A. Mood
Python Solution
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()
B. Hungry
Python Solution
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()
C. Ice Coffee
Python Solution
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()
D. Beautiful decrease
Python Solution
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()
E. The Detective Game
Python Solution
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()
F. Distinct
CPP Solution
#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();
}
}
G. String Rotation
Python Solution
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()
H. Cookies
Python Solution
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()
I. Omar and Trees
CPP Solution
#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();
}
}
J. Hide and Seek
Python Solution
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()
K. Wrong digits
Python Solution
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()
L. Black and White Tree
Python Solution
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()
M. Delivery
Python Solution
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()
N. How many rectangles?
Python Solution
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()
