### A. Mood↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
x, y = read_list()↵
print(max(0, y-x))↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### B. Hungry↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n = read()↵
a = read_list()↵
prefix_sum = [0]*(n+1)↵
for i in range(1, n+1):↵
prefix_sum[i] = prefix_sum[i-1] + a[i-1]↵
q = read()↵
for i in range(q):↵
x, y, m = read_list()↵
result = min(max(x, prefix_sum[n]), prefix_sum[m]+y)↵
print(result)↵
↵
↵
solve() ↵
```↵
</spoiler>↵
↵
### C. Ice Coffee↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
max_a = int(1e7)↵
nxt = [1] * (max_a+1)↵
↵
# modified sieve of eratosthenes↵
for i in range(2, max_a+1):↵
if nxt[i] == 1:↵
for j in range(i*i, max_a+1, i):↵
if nxt[j] == 1:↵
nxt[j] = j//i↵
↵
↵
def solve():↵
n = read()↵
a = read_list()↵
b = read_list()↵
result = 0↵
for i in range(n):↵
x = a[i]↵
y = b[i]↵
while x != y:↵
if x > y:↵
x = nxt[x]↵
else:↵
y = nxt[y]↵
result += 1↵
print(result)↵
↵
for i in range(read()):↵
solve()↵
↵
```↵
</spoiler>↵
↵
### D. Beautiful decrease↵
↵
<spoiler summary="Python Solution">↵
```python↵
↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
n, q = read_list()↵
a = read_list()↵
total = sum(a)↵
b_decreases = [] # (length, k)↵
↵
# monotonic stack↵
stack = [(0, -1)]↵
↵
↵
def mono_push(value, index):↵
if value > stack[-1][0]:↵
stack.append((value, index))↵
elif value < stack[-1][0]:↵
while value < stack[-1][0]:↵
if len(stack) > 1:↵
subarray_length = index-stack[-2][1]-1↵
k = min(stack[-1][0]-value, stack[-1][0]-stack[-2][0])↵
b_decreases.append([subarray_length, k])↵
stack.pop()↵
↵
if value != stack[-1][0]:↵
stack.append((value, index))↵
↵
↵
for i in range(n):↵
mono_push(a[i], i) ↵
mono_push(0, n)↵
↵
↵
↵
b_decreases.sort()↵
↵
for i in range(q):↵
k = read()↵
while len(b_decreases) > 0 and k > 0: ↵
decrease_count = min(k, b_decreases[-1][1])↵
total -= b_decreases[-1][0] * decrease_count↵
k -= decrease_count↵
b_decreases[-1][1] -= decrease_count↵
↵
if b_decreases[-1][1] == 0:↵
b_decreases.pop()↵
↵
print(total)↵
↵
↵
solve()↵
```↵
</spoiler>↵
↵
↵
### E. The Detective Game↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n = read()↵
count = [0] * (n+1)↵
for i in range(n):↵
for j in read_list()[1:]:↵
count[j] += 1↵
↵
result = []↵
for i in range(1, n+1):↵
if count[i] > n//2:↵
result.append(i)↵
print(len(result))↵
print(' '.join(map(str, result)))↵
↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### F. Distinct↵
↵
↵
<spoiler summary="CPP Solution">↵
```cpp↵
#include <cstdlib>↵
#include <cstring>↵
#include <cmath>↵
#include <iostream>↵
#include <stack>↵
#include <vector>↵
#include <array>↵
#include <queue>↵
#include <algorithm>↵
#include <map>↵
#include <set>↵
#include <unordered_map>↵
#include <unordered_set>↵
#include <numeric>↵
#include <string>↵
#include <iomanip>↵
#include <climits>↵
#include <functional>↵
#include <cctype>↵
#include <bitset>↵
#include <cassert>↵
↵
using namespace std; ↵
↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
template<typename T> using vec = vector<T>; ↵
using ull = uint64_t;↵
#define nl '\n'↵
#define MOD 1000000007↵
#define INF (LLONG_MAX/4)↵
↵
#define dbg(value) cerr << "#" #value << ": " << (value) << nl;↵
↵
template<typename type> ↵
struct matrix : vector<vector<type>> {↵
matrix(int N, int M, type Val = {}) : ↵
::vector<vector<type>>(N, vector<type>(M, Val)){} ↵
}; ↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
↵
struct MaxSegmentTree {↵
vec<int> tree;↵
int n;↵
↵
MaxSegmentTree(vec<int> const& arr) {↵
n = arr.size();↵
tree.assign(n*4, INT_MIN);↵
build(arr, 1, 0, n-1);↵
} ↵
void build(vec<int> const& arr, int i, int l, int r) {↵
if (l == r) {↵
tree[i] = arr[l];↵
} else {↵
int m = (l+r)/2;↵
build(arr, i*2, l, m);↵
build(arr, i*2+1, m+1, r);↵
tree[i] = max(tree[i*2], tree[i*2+1]);↵
}↵
}↵
↵
int get_max(int ql, int qr) {↵
return get_max(ql, qr, 1, 0, n-1);↵
} ↵
↵
int get_max(int ql, int qr, int i, int l, int r) {↵
if (ql > r || qr < l) return INT_MIN;↵
if (l >= ql && r <= qr) return tree[i];↵
int m = (l+r) / 2;↵
return max(get_max(ql, qr, i*2, l, m), get_max(ql, qr, i*2+1, m+1, r));↵
}↵
};↵
↵
struct MinSegmentTree {↵
vec<int> tree;↵
int n;↵
↵
MinSegmentTree(vec<int> const& arr) {↵
n = arr.size();↵
tree.assign(n*4, INT_MAX);↵
build(arr, 1, 0, n-1);↵
} ↵
void build(vec<int> const& arr, int i, int l, int r) {↵
if (l == r) {↵
tree[i] = arr[l];↵
} else {↵
int m = (l+r)/2;↵
build(arr, i*2, l, m);↵
build(arr, i*2+1, m+1, r);↵
tree[i] = min(tree[i*2], tree[i*2+1]);↵
}↵
}↵
↵
int first_less(int ql, int qr, int x) {↵
return first_less(ql, qr, x, 1, 0, n-1);↵
} ↵
↵
int first_less(int ql, int qr, int x, int i, int l, int r) {↵
if (ql > r || qr < l || tree[i] >= x) return -1;↵
if (l == r) return l;↵
int m = (l+r) / 2;↵
int left = first_less(ql, qr, x, i*2, l, m);↵
if (left != -1) return left;↵
return first_less(ql, qr, x, i*2+1, m+1, r);↵
}↵
};↵
↵
↵
↵
void solve() {↵
int n, q; cin >> n >> q;↵
vec<int> a(n);↵
vec<int> prefix_sum(n);↵
string line; cin >> line;↵
for (int i=0; i<n; i++) {↵
a[i] = (line[i] == '*') ? 1 : -1; ↵
}↵
↵
prefix_sum[0] = a[0];↵
for (int i=1; i<n; i++) {↵
prefix_sum[i] = prefix_sum[i-1] + a[i];↵
}↵
MinSegmentTree min_seg(prefix_sum);↵
MaxSegmentTree max_seg(prefix_sum);↵
↵
for (int i=0; i<q; i++) {↵
int l, r; cin >> l >> r;↵
l--; r--;↵
ll before = (l>0) ? prefix_sum[l-1] : 0; ↵
int zero_index = min_seg.first_less(l, r, before);↵
ll result = 1;↵
if (zero_index == -1) {↵
result += max(0ll, max_seg.get_max(l, r) - before); ↵
} else {↵
// x becomes zero in (l, r)↵
result += 1 + max(0ll, max_seg.get_max(l, zero_index) - before); ↵
}↵
cout << result << nl;↵
}↵
↵
}↵
↵
↵
int main(int argc, char** argv) {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
// preprocess();↵
↵
int t=1;↵
cin >> t;↵
for (int i=0; i<t; i++){↵
solve();↵
}↵
↵
}↵
↵
```↵
</spoiler>↵
↵
### G. String Rotation↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n, x = read_list()↵
s = input()↵
t = input()↵
result = 0↵
for i in range(n):↵
j = (i+n-x%n)%n↵
if t[i] != s[j]:↵
result += 1↵
print(result)↵
↵
solve()↵
```↵
</spoiler>↵
↵
### H. Cookies↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n, m, a = read_list()↵
print(min(n-m, a))↵
↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### I. Omar and Trees↵
↵
<spoiler summary="CPP Solution">↵
```cpp#include <cstdlib>↵
#include <cstring>↵
#include <cmath>↵
#include <iostream>↵
#include <stack>↵
#include <vector>↵
#include <array>↵
#include <queue>↵
#include <algorithm>↵
#include <map>↵
#include <set>↵
#include <unordered_map>↵
#include <unordered_set>↵
#include <numeric>↵
#include <string>↵
#include <iomanip>↵
#include <climits>↵
#include <functional>↵
#include <cctype>↵
#include <bitset>↵
#include <cassert>↵
↵
using namespace std; ↵
↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
template<typename T> using vec = vector<T>; ↵
using ull = uint64_t;↵
#define nl '\n'↵
#define MOD 1000000007↵
#define INF (LLONG_MAX/4)↵
↵
#define dbg(value) cerr << "#" #value << ": " << (value) << nl;↵
↵
template<typename type> ↵
struct matrix : vector<vector<type>> {↵
matrix(int N, int M, type Val = {}) : ↵
::vector<vector<type>>(N, vector<type>(M, Val)){} ↵
}; ↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
↵
↵
struct SegmentTree {↵
// segment tree with lazy propagation↵
↵
vec<ll> tree;↵
vec<ll> updated;↵
int n;↵
↵
SegmentTree(int n) : n(n), tree(n*4), updated(n*4, -1) {}↵
↵
void build(vec<int> const &a) {↵
build(a, 1, 0, n-1);↵
} ↵
void build(vec<int> const &a, int i, int l, int r) {↵
if (l == r) {↵
tree[i] = a[l];↵
} else {↵
int m = (l+r)/2;↵
build(a, i*2, l, m);↵
build(a, i*2+1, m+1, r);↵
tree[i] = tree[i*2] + tree[i*2+1];↵
}↵
}↵
↵
void push(int i, int l, int r) {↵
if (updated[i] != -1 && l != r){↵
int m = (l+r)/2;↵
tree[i*2] = (m-l+1) * updated[i];↵
tree[i*2+1] = (r-m) * updated[i];↵
updated[i*2] = updated[i];↵
updated[i*2+1] = updated[i];↵
}↵
updated[i] = -1;↵
↵
}↵
↵
ll sum(int ql, int qr) {↵
return sum(ql, qr, 1, 0, n-1);↵
}↵
↵
ll sum(int ql, int qr, int i, int l, int r) {↵
if (ql > r || qr < l) return 0;↵
push(i, l, r);↵
↵
if (ql <= l && qr >= r) {↵
return tree[i];↵
} else {↵
int m = (l+r)/2;↵
ll result = sum(ql, qr, i*2, l, m) + sum(ql, qr, i*2+1, m+1, r);↵
return result;↵
}↵
}↵
↵
↵
void update_range(int ql, int qr, ll val) {↵
update_range(ql, qr, val, 1, 0, n-1);↵
}↵
↵
void update_range(int ql, int qr, ll val, int i, int l, int r) {↵
if (ql > r || qr < l) return;↵
if (ql <= l && qr >= r) {↵
tree[i] = val * (r-l+1);↵
updated[i] = val;↵
} else {↵
int m = (l+r)/2;↵
push(i, l, r);↵
update_range(ql, qr, val, i*2, l, m);↵
update_range(ql, qr, val, i*2+1, m+1, r);↵
tree[i] = tree[i*2] + tree[i*2+1];↵
}↵
}↵
↵
↵
};↵
↵
↵
bool check_prime(ll x) {↵
for (ll d = 2; d * d <= x; d++) {↵
if (x % d == 0)↵
return false;↵
}↵
return x >= 2;↵
}↵
↵
↵
↵
↵
vec<vec<int>> adj;↵
vec<int> traversal_map;↵
vec<int> traversal_map_out;↵
int dfs_index;↵
↵
void dfs(int node, int prev = -1) {↵
traversal_map[node] = dfs_index++;↵
for (int i: adj[node]) {↵
if (i != prev) {↵
dfs(i, node);↵
}↵
}↵
traversal_map_out[node] = dfs_index-1;↵
}↵
↵
void solve() {↵
int n; cin >> n;↵
vec<int> values(n);↵
adj.resize(n);↵
traversal_map.resize(n);↵
traversal_map_out.resize(n);↵
↵
for (int i=0; i<n; i++) {↵
cin >> values[i];↵
}↵
↵
for (int i=0; i<n-1; i++) {↵
int a, b; cin >> a >> b;↵
a--; b--;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
↵
dfs_index = 0;↵
dfs(0);↵
↵
SegmentTree st(n);↵
vec<int> traveral_values(n);↵
for (int i=0; i<n; i++) {↵
traveral_values[traversal_map[i]] = values[i];↵
}↵
st.build(traveral_values);↵
↵
↵
int q; cin >> q;↵
for (int i=0; i<q; i++) {↵
int t; cin >> t;↵
if (t == 2) {↵
int u; cin >> u;↵
u--;↵
ll s = st.sum(traversal_map[u], traversal_map_out[u]);↵
↵
// Goldbach’s conjecture states that all even integers can be the sum of ↵
// 2 primes↵
// for odd numbers the sum of 2 primes should be equal to 2 + p where p is ↵
// a prime ↵
if (s >= 4 && (s%2 == 0 || check_prime(s - 2))) {↵
cout << "YES" << nl;↵
} else {↵
cout << "NO" << nl;↵
}↵
↵
} else {↵
int u, val; cin >> u >> val;↵
u--;↵
st.update_range(traversal_map[u], traversal_map_out[u], val);↵
}↵
}↵
}↵
↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
// preprocess();↵
↵
int t=1;↵
// cin >> t;↵
for (int i=0; i<t; i++){↵
solve();↵
}↵
↵
}↵
```↵
</spoiler>↵
↵
↵
### J. Hide and Seek ↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n, x = read_list()↵
h = read_list()↵
result = [0] * n↵
for i in range(n):↵
if h[i] < x:↵
result[i] = 1↵
print(' '.join(map(str, result))) ↵
↵
↵
for i in range(read()):↵
solve() ↵
```↵
</spoiler>↵
↵
↵
### K. Wrong digits↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
bits = {}↵
↵
# bitmask of digit dashes↵
bits['0'] = 0x77;↵
bits['1'] = 0x12;↵
bits['2'] = 0x5D;↵
bits['3'] = 0x5B;↵
bits['4'] = 0x3A;↵
bits['5'] = 0x6B;↵
bits['6'] = 0x6F;↵
bits['7'] = 0x52;↵
bits['8'] = 0x7F;↵
bits['9'] = 0x7B;↵
↵
def solve():↵
n, x, y = read_list()↵
s = input()↵
t = input()↵
↵
dp = [[-1] * (y+1) for i in range(x+1)]↵
dp[0][0] = 0;↵
↵
for i in range(n):↵
for j in range(x+1):↵
for k in range(y+1):↵
if dp[j][k] == i:↵
for c in range(ord('0'), ord('9')+1):↵
org1 = bits[s[i]]↵
org2 = bits[t[i]]↵
dst = bits[chr(c)]↵
j2 = j↵
k2 = k↵
j2 += ((~dst) & org1).bit_count()↵
j2 += ((~dst) & org2).bit_count()↵
k2 += ((~org1) & dst).bit_count()↵
k2 += ((~org2) & dst).bit_count()↵
↵
if j2 <= x and k2 <= y:↵
dp[j2][k2] = max(dp[j2][k2], i+1)↵
if dp[j2][k2] == n:↵
print("YES")↵
return↵
print("NO")↵
↵
↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### L. Black and White Tree↵
↵
<spoiler summary="Python Solution">↵
```python↵
↵
from types import GeneratorType↵
def stackless(f, stack=[]):↵
# use this on to avoid stack overflow↵
def wrappedfunc(*args, **kwargs):↵
if stack:↵
return f(*args, **kwargs)↵
else:↵
to = f(*args, **kwargs)↵
while True:↵
if type(to) is GeneratorType:↵
stack.append(to)↵
to = next(to)↵
else:↵
stack.pop()↵
if not stack:↵
break↵
to = stack[-1].send(to)↵
return to↵
return wrappedfunc↵
↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
n, q = read_list()↵
color = [1 if i else -1 for i in read_list()]↵
g = [[] for i in range(n)] ↵
result = [0] * n↵
for i in range(n-1):↵
a, b = read_list()↵
a -= 1↵
b -= 1↵
g[a].append(b)↵
g[b].append(a)↵
↵
@stackless↵
def dfs(node=0, prev=-1, prev_sum=0):↵
freq = {} # count of all possible sums (starting from the root) of color values in this subtree ↵
s = color[node] + prev_sum↵
for i in g[node]: ↵
if i != prev:↵
next_freq = yield dfs(i, node, s)↵
if len(next_freq) > len(freq): ↵
next_freq, freq = freq, next_freq↵
for k, v in next_freq.items():↵
freq[k] = freq.get(k, 0) + v↵
↵
↵
# zero sums means the number of black nodes and white node are equal↵
# sums start at the root so instead of subtracting prev_sum from all values ↵
# in freq we can add prev_sum to the value we're looking for which is 0↵
result[node] = freq.get(prev_sum, 0) ↵
freq[s] = freq.get(s, 0) + 1↵
yield freq↵
dfs()↵
↵
print('\n'.join(map(str, result)))↵
↵
↵
↵
solve()↵
```↵
</spoiler>↵
↵
↵
### M. Delivery↵
↵
<spoiler summary="Python Solution">↵
```python ↵
↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
n = read()↵
x = n↵
while x%2 == 0:↵
x //= 2↵
↵
if x == 1:↵
print(-1)↵
return ↵
↵
l = x//2↵
r = x//2+1↵
↵
d = n // x↵
↵
r += d-1↵
l -= d-1↵
if l < 0:↵
l = -l + 1↵
↵
print(l, r)↵
↵
↵
for i in range(read()):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
### N. How many rectangles?↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
↵
class FenwickTree:↵
def __init__(self, n):↵
self.a = [0] * (n+1)↵
self.n = n↵
↵
def prefix_sum(self, k):↵
s = 0↵
while k >= 1:↵
s += self.a[k]↵
k -= k&-k↵
return s↵
↵
def add(self, k, v):↵
while k <= self.n:↵
self.a[k] += v↵
k += k&-k↵
↵
↵
def solve():↵
n = read()↵
points = [] # (x, y, query index)↵
compress = {}↵
for i in range(n):↵
_, _, x, y = read_list()↵
compress[x] = 0↵
compress[y] = 0↵
points.append([x, y, -1])↵
↵
q = read()↵
result = [0] * q↵
for i in range(q):↵
x, y = read_list()↵
compress[x] = 0↵
compress[y] = 0↵
points.append([x, y, i])↵
↵
points.sort()↵
↵
compress_index = 1↵
for i in sorted(compress.keys()):↵
compress[i] = compress_index↵
compress_index += 1↵
↵
ft = FenwickTree(len(compress))↵
for x, y, q in points:↵
if q == -1:↵
ft.add(compress[y], 1)↵
else:↵
result[q] = ft.prefix_sum(compress[y])↵
↵
print('\n'.join(map(str, result)))↵
↵
solve()↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
x, y = read_list()↵
print(max(0, y-x))↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### B. Hungry↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n = read()↵
a = read_list()↵
prefix_sum = [0]*(n+1)↵
for i in range(1, n+1):↵
prefix_sum[i] = prefix_sum[i-1] + a[i-1]↵
q = read()↵
for i in range(q):↵
x, y, m = read_list()↵
result = min(max(x, prefix_sum[n]), prefix_sum[m]+y)↵
print(result)↵
↵
↵
solve() ↵
```↵
</spoiler>↵
↵
### C. Ice Coffee↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
max_a = int(1e7)↵
nxt = [1] * (max_a+1)↵
↵
# modified sieve of eratosthenes↵
for i in range(2, max_a+1):↵
if nxt[i] == 1:↵
for j in range(i*i, max_a+1, i):↵
if nxt[j] == 1:↵
nxt[j] = j//i↵
↵
↵
def solve():↵
n = read()↵
a = read_list()↵
b = read_list()↵
result = 0↵
for i in range(n):↵
x = a[i]↵
y = b[i]↵
while x != y:↵
if x > y:↵
x = nxt[x]↵
else:↵
y = nxt[y]↵
result += 1↵
print(result)↵
↵
for i in range(read()):↵
solve()↵
↵
```↵
</spoiler>↵
↵
### D. Beautiful decrease↵
↵
<spoiler summary="Python Solution">↵
```python↵
↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
n, q = read_list()↵
a = read_list()↵
total = sum(a)↵
b_decreases = [] # (length, k)↵
↵
# monotonic stack↵
stack = [(0, -1)]↵
↵
↵
def mono_push(value, index):↵
if value > stack[-1][0]:↵
stack.append((value, index))↵
elif value < stack[-1][0]:↵
while value < stack[-1][0]:↵
if len(stack) > 1:↵
subarray_length = index-stack[-2][1]-1↵
k = min(stack[-1][0]-value, stack[-1][0]-stack[-2][0])↵
b_decreases.append([subarray_length, k])↵
stack.pop()↵
↵
if value != stack[-1][0]:↵
stack.append((value, index))↵
↵
↵
for i in range(n):↵
mono_push(a[i], i) ↵
mono_push(0, n)↵
↵
↵
↵
b_decreases.sort()↵
↵
for i in range(q):↵
k = read()↵
while len(b_decreases) > 0 and k > 0: ↵
decrease_count = min(k, b_decreases[-1][1])↵
total -= b_decreases[-1][0] * decrease_count↵
k -= decrease_count↵
b_decreases[-1][1] -= decrease_count↵
↵
if b_decreases[-1][1] == 0:↵
b_decreases.pop()↵
↵
print(total)↵
↵
↵
solve()↵
```↵
</spoiler>↵
↵
↵
### E. The Detective Game↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n = read()↵
count = [0] * (n+1)↵
for i in range(n):↵
for j in read_list()[1:]:↵
count[j] += 1↵
↵
result = []↵
for i in range(1, n+1):↵
if count[i] > n//2:↵
result.append(i)↵
print(len(result))↵
print(' '.join(map(str, result)))↵
↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### F. Distinct↵
↵
↵
<spoiler summary="CPP Solution">↵
```cpp↵
#include <cstdlib>↵
#include <cstring>↵
#include <cmath>↵
#include <iostream>↵
#include <stack>↵
#include <vector>↵
#include <array>↵
#include <queue>↵
#include <algorithm>↵
#include <map>↵
#include <set>↵
#include <unordered_map>↵
#include <unordered_set>↵
#include <numeric>↵
#include <string>↵
#include <iomanip>↵
#include <climits>↵
#include <functional>↵
#include <cctype>↵
#include <bitset>↵
#include <cassert>↵
↵
using namespace std; ↵
↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
template<typename T> using vec = vector<T>; ↵
using ull = uint64_t;↵
#define nl '\n'↵
#define MOD 1000000007↵
#define INF (LLONG_MAX/4)↵
↵
#define dbg(value) cerr << "#" #value << ": " << (value) << nl;↵
↵
template<typename type> ↵
struct matrix : vector<vector<type>> {↵
matrix(int N, int M, type Val = {}) : ↵
::vector<vector<type>>(N, vector<type>(M, Val)){} ↵
}; ↵
↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
↵
struct MaxSegmentTree {↵
vec<int> tree;↵
int n;↵
↵
MaxSegmentTree(vec<int> const& arr) {↵
n = arr.size();↵
tree.assign(n*4, INT_MIN);↵
build(arr, 1, 0, n-1);↵
} ↵
void build(vec<int> const& arr, int i, int l, int r) {↵
if (l == r) {↵
tree[i] = arr[l];↵
} else {↵
int m = (l+r)/2;↵
build(arr, i*2, l, m);↵
build(arr, i*2+1, m+1, r);↵
tree[i] = max(tree[i*2], tree[i*2+1]);↵
}↵
}↵
↵
int get_max(int ql, int qr) {↵
return get_max(ql, qr, 1, 0, n-1);↵
} ↵
↵
int get_max(int ql, int qr, int i, int l, int r) {↵
if (ql > r || qr < l) return INT_MIN;↵
if (l >= ql && r <= qr) return tree[i];↵
int m = (l+r) / 2;↵
return max(get_max(ql, qr, i*2, l, m), get_max(ql, qr, i*2+1, m+1, r));↵
}↵
};↵
↵
struct MinSegmentTree {↵
vec<int> tree;↵
int n;↵
↵
MinSegmentTree(vec<int> const& arr) {↵
n = arr.size();↵
tree.assign(n*4, INT_MAX);↵
build(arr, 1, 0, n-1);↵
} ↵
void build(vec<int> const& arr, int i, int l, int r) {↵
if (l == r) {↵
tree[i] = arr[l];↵
} else {↵
int m = (l+r)/2;↵
build(arr, i*2, l, m);↵
build(arr, i*2+1, m+1, r);↵
tree[i] = min(tree[i*2], tree[i*2+1]);↵
}↵
}↵
↵
int first_less(int ql, int qr, int x) {↵
return first_less(ql, qr, x, 1, 0, n-1);↵
} ↵
↵
int first_less(int ql, int qr, int x, int i, int l, int r) {↵
if (ql > r || qr < l || tree[i] >= x) return -1;↵
if (l == r) return l;↵
int m = (l+r) / 2;↵
int left = first_less(ql, qr, x, i*2, l, m);↵
if (left != -1) return left;↵
return first_less(ql, qr, x, i*2+1, m+1, r);↵
}↵
};↵
↵
↵
↵
void solve() {↵
int n, q; cin >> n >> q;↵
vec<int> a(n);↵
vec<int> prefix_sum(n);↵
string line; cin >> line;↵
for (int i=0; i<n; i++) {↵
a[i] = (line[i] == '*') ? 1 : -1; ↵
}↵
↵
prefix_sum[0] = a[0];↵
for (int i=1; i<n; i++) {↵
prefix_sum[i] = prefix_sum[i-1] + a[i];↵
}↵
MinSegmentTree min_seg(prefix_sum);↵
MaxSegmentTree max_seg(prefix_sum);↵
↵
for (int i=0; i<q; i++) {↵
int l, r; cin >> l >> r;↵
l--; r--;↵
ll before = (l>0) ? prefix_sum[l-1] : 0; ↵
int zero_index = min_seg.first_less(l, r, before);↵
ll result = 1;↵
if (zero_index == -1) {↵
result += max(0ll, max_seg.get_max(l, r) - before); ↵
} else {↵
// x becomes zero in (l, r)↵
result += 1 + max(0ll, max_seg.get_max(l, zero_index) - before); ↵
}↵
cout << result << nl;↵
}↵
↵
}↵
↵
↵
int main(int argc, char** argv) {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
// preprocess();↵
↵
int t=1;↵
cin >> t;↵
for (int i=0; i<t; i++){↵
solve();↵
}↵
↵
}↵
↵
```↵
</spoiler>↵
↵
### G. String Rotation↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n, x = read_list()↵
s = input()↵
t = input()↵
result = 0↵
for i in range(n):↵
j = (i+n-x%n)%n↵
if t[i] != s[j]:↵
result += 1↵
print(result)↵
↵
solve()↵
```↵
</spoiler>↵
↵
### H. Cookies↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n, m, a = read_list()↵
print(min(n-m, a))↵
↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### I. Omar and Trees↵
↵
<spoiler summary="CPP Solution">↵
```cpp#include <cstdlib>↵
#include <cstring>↵
#include <cmath>↵
#include <iostream>↵
#include <stack>↵
#include <vector>↵
#include <array>↵
#include <queue>↵
#include <algorithm>↵
#include <map>↵
#include <set>↵
#include <unordered_map>↵
#include <unordered_set>↵
#include <numeric>↵
#include <string>↵
#include <iomanip>↵
#include <climits>↵
#include <functional>↵
#include <cctype>↵
#include <bitset>↵
#include <cassert>↵
↵
using namespace std; ↵
↵
#define all(a) a.begin(), a.end()↵
using ll = long long;↵
template<typename T> using vec = vector<T>; ↵
using ull = uint64_t;↵
#define nl '\n'↵
#define MOD 1000000007↵
#define INF (LLONG_MAX/4)↵
↵
#define dbg(value) cerr << "#" #value << ": " << (value) << nl;↵
↵
template<typename type> ↵
struct matrix : vector<vector<type>> {↵
matrix(int N, int M, type Val = {}) : ↵
::vector<vector<type>>(N, vector<type>(M, Val)){} ↵
}; ↵
template<typename T> ↵
using min_heap = priority_queue<T, vector<T>, greater<T>>;↵
↵
↵
↵
struct SegmentTree {↵
// segment tree with lazy propagation↵
↵
vec<ll> tree;↵
vec<ll> updated;↵
int n;↵
↵
SegmentTree(int n) : n(n), tree(n*4), updated(n*4, -1) {}↵
↵
void build(vec<int> const &a) {↵
build(a, 1, 0, n-1);↵
} ↵
void build(vec<int> const &a, int i, int l, int r) {↵
if (l == r) {↵
tree[i] = a[l];↵
} else {↵
int m = (l+r)/2;↵
build(a, i*2, l, m);↵
build(a, i*2+1, m+1, r);↵
tree[i] = tree[i*2] + tree[i*2+1];↵
}↵
}↵
↵
void push(int i, int l, int r) {↵
if (updated[i] != -1 && l != r){↵
int m = (l+r)/2;↵
tree[i*2] = (m-l+1) * updated[i];↵
tree[i*2+1] = (r-m) * updated[i];↵
updated[i*2] = updated[i];↵
updated[i*2+1] = updated[i];↵
}↵
updated[i] = -1;↵
↵
}↵
↵
ll sum(int ql, int qr) {↵
return sum(ql, qr, 1, 0, n-1);↵
}↵
↵
ll sum(int ql, int qr, int i, int l, int r) {↵
if (ql > r || qr < l) return 0;↵
push(i, l, r);↵
↵
if (ql <= l && qr >= r) {↵
return tree[i];↵
} else {↵
int m = (l+r)/2;↵
ll result = sum(ql, qr, i*2, l, m) + sum(ql, qr, i*2+1, m+1, r);↵
return result;↵
}↵
}↵
↵
↵
void update_range(int ql, int qr, ll val) {↵
update_range(ql, qr, val, 1, 0, n-1);↵
}↵
↵
void update_range(int ql, int qr, ll val, int i, int l, int r) {↵
if (ql > r || qr < l) return;↵
if (ql <= l && qr >= r) {↵
tree[i] = val * (r-l+1);↵
updated[i] = val;↵
} else {↵
int m = (l+r)/2;↵
push(i, l, r);↵
update_range(ql, qr, val, i*2, l, m);↵
update_range(ql, qr, val, i*2+1, m+1, r);↵
tree[i] = tree[i*2] + tree[i*2+1];↵
}↵
}↵
↵
↵
};↵
↵
↵
bool check_prime(ll x) {↵
for (ll d = 2; d * d <= x; d++) {↵
if (x % d == 0)↵
return false;↵
}↵
return x >= 2;↵
}↵
↵
↵
↵
↵
vec<vec<int>> adj;↵
vec<int> traversal_map;↵
vec<int> traversal_map_out;↵
int dfs_index;↵
↵
void dfs(int node, int prev = -1) {↵
traversal_map[node] = dfs_index++;↵
for (int i: adj[node]) {↵
if (i != prev) {↵
dfs(i, node);↵
}↵
}↵
traversal_map_out[node] = dfs_index-1;↵
}↵
↵
void solve() {↵
int n; cin >> n;↵
vec<int> values(n);↵
adj.resize(n);↵
traversal_map.resize(n);↵
traversal_map_out.resize(n);↵
↵
for (int i=0; i<n; i++) {↵
cin >> values[i];↵
}↵
↵
for (int i=0; i<n-1; i++) {↵
int a, b; cin >> a >> b;↵
a--; b--;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
↵
dfs_index = 0;↵
dfs(0);↵
↵
SegmentTree st(n);↵
vec<int> traveral_values(n);↵
for (int i=0; i<n; i++) {↵
traveral_values[traversal_map[i]] = values[i];↵
}↵
st.build(traveral_values);↵
↵
↵
int q; cin >> q;↵
for (int i=0; i<q; i++) {↵
int t; cin >> t;↵
if (t == 2) {↵
int u; cin >> u;↵
u--;↵
ll s = st.sum(traversal_map[u], traversal_map_out[u]);↵
↵
// Goldbach’s conjecture states that all even integers can be the sum of ↵
// 2 primes↵
// for odd numbers the sum of 2 primes should be equal to 2 + p where p is ↵
// a prime ↵
if (s >= 4 && (s%2 == 0 || check_prime(s - 2))) {↵
cout << "YES" << nl;↵
} else {↵
cout << "NO" << nl;↵
}↵
↵
} else {↵
int u, val; cin >> u >> val;↵
u--;↵
st.update_range(traversal_map[u], traversal_map_out[u], val);↵
}↵
}↵
}↵
↵
↵
↵
int main() {↵
#ifndef ONLINE_JUDGE ↵
freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
#else↵
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
#endif↵
// preprocess();↵
↵
int t=1;↵
// cin >> t;↵
for (int i=0; i<t; i++){↵
solve();↵
}↵
↵
}↵
```↵
</spoiler>↵
↵
↵
### J. Hide and Seek ↵
↵
<spoiler summary="Python Solution">↵
```python ↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
def solve():↵
n, x = read_list()↵
h = read_list()↵
result = [0] * n↵
for i in range(n):↵
if h[i] < x:↵
result[i] = 1↵
print(' '.join(map(str, result))) ↵
↵
↵
for i in range(read()):↵
solve() ↵
```↵
</spoiler>↵
↵
↵
### K. Wrong digits↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
bits = {}↵
↵
# bitmask of digit dashes↵
bits['0'] = 0x77;↵
bits['1'] = 0x12;↵
bits['2'] = 0x5D;↵
bits['3'] = 0x5B;↵
bits['4'] = 0x3A;↵
bits['5'] = 0x6B;↵
bits['6'] = 0x6F;↵
bits['7'] = 0x52;↵
bits['8'] = 0x7F;↵
bits['9'] = 0x7B;↵
↵
def solve():↵
n, x, y = read_list()↵
s = input()↵
t = input()↵
↵
dp = [[-1] * (y+1) for i in range(x+1)]↵
dp[0][0] = 0;↵
↵
for i in range(n):↵
for j in range(x+1):↵
for k in range(y+1):↵
if dp[j][k] == i:↵
for c in range(ord('0'), ord('9')+1):↵
org1 = bits[s[i]]↵
org2 = bits[t[i]]↵
dst = bits[chr(c)]↵
j2 = j↵
k2 = k↵
j2 += ((~dst) & org1).bit_count()↵
j2 += ((~dst) & org2).bit_count()↵
k2 += ((~org1) & dst).bit_count()↵
k2 += ((~org2) & dst).bit_count()↵
↵
if j2 <= x and k2 <= y:↵
dp[j2][k2] = max(dp[j2][k2], i+1)↵
if dp[j2][k2] == n:↵
print("YES")↵
return↵
print("NO")↵
↵
↵
↵
for i in range(read()):↵
solve()↵
```↵
</spoiler>↵
↵
### L. Black and White Tree↵
↵
<spoiler summary="Python Solution">↵
```python↵
↵
from types import GeneratorType↵
def stackless(f, stack=[]):↵
# use this on to avoid stack overflow↵
def wrappedfunc(*args, **kwargs):↵
if stack:↵
return f(*args, **kwargs)↵
else:↵
to = f(*args, **kwargs)↵
while True:↵
if type(to) is GeneratorType:↵
stack.append(to)↵
to = next(to)↵
else:↵
stack.pop()↵
if not stack:↵
break↵
to = stack[-1].send(to)↵
return to↵
return wrappedfunc↵
↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
n, q = read_list()↵
color = [1 if i else -1 for i in read_list()]↵
g = [[] for i in range(n)] ↵
result = [0] * n↵
for i in range(n-1):↵
a, b = read_list()↵
a -= 1↵
b -= 1↵
g[a].append(b)↵
g[b].append(a)↵
↵
@stackless↵
def dfs(node=0, prev=-1, prev_sum=0):↵
freq = {} # count of all possible sums (starting from the root) of color values in this subtree ↵
s = color[node] + prev_sum↵
for i in g[node]: ↵
if i != prev:↵
next_freq = yield dfs(i, node, s)↵
if len(next_freq) > len(freq): ↵
next_freq, freq = freq, next_freq↵
for k, v in next_freq.items():↵
freq[k] = freq.get(k, 0) + v↵
↵
↵
# zero sums means the number of black nodes and white node are equal↵
# sums start at the root so instead of subtracting prev_sum from all values ↵
# in freq we can add prev_sum to the value we're looking for which is 0↵
result[node] = freq.get(prev_sum, 0) ↵
freq[s] = freq.get(s, 0) + 1↵
yield freq↵
dfs()↵
↵
print('\n'.join(map(str, result)))↵
↵
↵
↵
solve()↵
```↵
</spoiler>↵
↵
↵
### M. Delivery↵
↵
<spoiler summary="Python Solution">↵
```python ↵
↵
def read():↵
return int(input())↵
↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
def solve():↵
n = read()↵
x = n↵
while x%2 == 0:↵
x //= 2↵
↵
if x == 1:↵
print(-1)↵
return ↵
↵
l = x//2↵
r = x//2+1↵
↵
d = n // x↵
↵
r += d-1↵
l -= d-1↵
if l < 0:↵
l = -l + 1↵
↵
print(l, r)↵
↵
↵
for i in range(read()):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
### N. How many rectangles?↵
↵
<spoiler summary="Python Solution">↵
```python↵
def read():↵
return int(input())↵
def read_list():↵
return [int(i) for i in input().split()]↵
↵
↵
↵
class FenwickTree:↵
def __init__(self, n):↵
self.a = [0] * (n+1)↵
self.n = n↵
↵
def prefix_sum(self, k):↵
s = 0↵
while k >= 1:↵
s += self.a[k]↵
k -= k&-k↵
return s↵
↵
def add(self, k, v):↵
while k <= self.n:↵
self.a[k] += v↵
k += k&-k↵
↵
↵
def solve():↵
n = read()↵
points = [] # (x, y, query index)↵
compress = {}↵
for i in range(n):↵
_, _, x, y = read_list()↵
compress[x] = 0↵
compress[y] = 0↵
points.append([x, y, -1])↵
↵
q = read()↵
result = [0] * q↵
for i in range(q):↵
x, y = read_list()↵
compress[x] = 0↵
compress[y] = 0↵
points.append([x, y, i])↵
↵
points.sort()↵
↵
compress_index = 1↵
for i in sorted(compress.keys()):↵
compress[i] = compress_index↵
compress_index += 1↵
↵
ft = FenwickTree(len(compress))↵
for x, y, q in points:↵
if q == -1:↵
ft.add(compress[y], 1)↵
else:↵
result[q] = ft.prefix_sum(compress[y])↵
↵
print('\n'.join(map(str, result)))↵
↵
solve()↵
```↵
</spoiler>↵
↵
