TCPC 20202 Solutions
Difference between en4 and en5, changed 2 character(s)
### 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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English ammar007 2024-08-28 01:51:04 0 (published)
en5 English ammar007 2024-08-28 01:50:50 2 (saved to drafts)
en4 English ammar007 2024-08-28 01:50:17 0 (published)
en3 English ammar007 2024-08-28 01:47:48 167
en2 English ammar007 2024-08-28 01:46:45 16570
en1 English ammar007 2024-08-27 16:47:30 5396 Initial revision (saved to drafts)