1843A - Sasha and Array Coloring
Идея: EJIC_B_KEDAX, разработка: molney
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 0
for i in range(n // 2):
ans += a[-i-1] - a[i]
print(ans)
t = int(input())
for _ in range(t):
solve()
Идея: EJIC_B_KEDAX, разработка: molney
Разбор
Tutorial is loading...
Решение
T = int(input())
for _ in range(T):
n = int(input())
a = list(map(int, input().split()))
sum = 0
cnt = 0
open = False
for x in a:
sum += abs(x)
if x < 0 and not open:
open = True
cnt += 1
if x > 0:
open = False
print(sum, cnt)
Идея: Sokol080808, разработка: molney
Разбор
Tutorial is loading...
Решение
t = int(input())
for _ in range(t):
n = int(input())
s = 0
while n >= 1:
s += n
n //= 2
print(s)
Идея: EJIC_B_KEDAX, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> g;
vector<ll> cnt;
void dfs(int v, int p) {
if (g[v].size() == 1 && g[v][0] == p) {
cnt[v] = 1;
} else {
for (auto u : g[v]) {
if (u != p) {
dfs(u, v);
cnt[v] += cnt[u];
}
}
}
}
void solve() {
int n, q;
cin >> n;
g.assign(n, vector<int>());
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
cnt.assign(n, 0);
dfs(0, -1);
cin >> q;
for (int i = 0; i < q; i++) {
int c, k;
cin >> c >> k;
c--; k--;
ll res = cnt[c] * cnt[k];
cout << res << '\n';
}
}
signed main() {
int tests;
cin >> tests;
while (tests--) {
solve();
}
return 0;
}
Идея: meowcneil, разработка: meowcneil
Разбор
Tutorial is loading...
Решение
def solve():
n, m = map(int, input().split())
segs = []
for i in range(m):
l, r = map(int, input().split())
l -= 1
segs.append([l, r])
q = int(input())
ord = [0] * q
for i in range(q):
ord[i] = int(input())
ord[i] -= 1
l = 0
r = q + 1
while r - l > 1:
M = (l + r) // 2
cur = [0] * n
for i in range(M):
cur[ord[i]] = 1
pr = [0] * (n + 1)
for i in range(n):
pr[i+1] = pr[i] + cur[i]
ok = False
for i in segs:
if(pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2):
ok = True
break
if ok:
r = M
else:
l = M
if r == q + 1:
r = -1
print(r)
tc = int(input())
for T in range(tc):
solve()
1843F1 - Omsk Metro (simple version)
Идея: EJIC_B_KEDAX, разработка: Sokol080808
Разбор
Tutorial is loading...
Решение
class info:
mn_suf = 0
mx_suf = 0
mn_ans = 0
mx_ans = 0
def solve():
n = int(input())
start = info()
start.mx_suf = start.mx_ans = 1
st = [start]
for i in range(n):
com = input().split()
if (com[0] == '+'):
v = int(com[1]) - 1
x = int(com[2])
pref = st[v]
cur = info()
cur.mn_suf = min(0, pref.mn_suf + x)
cur.mx_suf = max(0, pref.mx_suf + x)
cur.mn_ans = min(pref.mn_ans, cur.mn_suf)
cur.mx_ans = max(pref.mx_ans, cur.mx_suf)
st.append(cur)
else:
v = int(com[2]) - 1
x = int(com[3])
if st[v].mn_ans <= x <= st[v].mx_ans:
print("Yes")
else:
print("No")
t = int(input())
for testCase in range(t):
solve()
1843F2 - Omsk Metro (hard version)
Идея: EJIC_B_KEDAX, разработка: Sokol080808
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct info {
int sum, minPrefL, maxPrefL, minPrefR, maxPrefR, minSeg, maxSeg;
info(int el = 0) {
sum = el;
minSeg = minPrefL = minPrefR = min(el, 0);
maxSeg = maxPrefL = maxPrefR = max(el, 0);
}
};
struct question {
int u, v, x;
};
info merge(info& a, info& b) {
info res;
res.sum = a.sum + b.sum;
res.minPrefL = min(a.minPrefL, a.sum + b.minPrefL);
res.maxPrefL = max(a.maxPrefL, a.sum + b.maxPrefL);
res.minPrefR = min(a.minPrefR + b.sum, b.minPrefR);
res.maxPrefR = max(a.maxPrefR + b.sum, b.maxPrefR);
res.minSeg = min({a.minSeg, b.minSeg, a.minPrefR + b.minPrefL});
res.maxSeg = max({a.maxSeg, b.maxSeg, a.maxPrefR + b.maxPrefL});
return res;
}
const int MAXN = 200100;
const int lg = 17;
int up[lg + 1][MAXN];
info ans[lg + 1][MAXN];
int d[MAXN];
void solve() {
int n;
cin >> n;
for (int i = 0; i <= lg; i++) up[i][0] = 0;
ans[0][0] = info(1);
d[0] = 0;
int cur = 0;
for (int q = 0; q < n; q++) {
char c;
cin >> c;
if (c == '+') {
int v, x;
cin >> v >> x;
v--;
cur++;
d[cur] = d[v] + 1;
up[0][cur] = v;
for (int j = 0; j <= lg - 1; j++) up[j + 1][cur] = up[j][up[j][cur]];
ans[0][cur] = info(x);
for (int j = 0; j <= lg - 1; j++) ans[j + 1][cur] = merge(ans[j][cur], ans[j][up[j][cur]]);
} else {
int u, v, x;
cin >> u >> v >> x;
u--; v--;
if (d[u] < d[v]) swap(u, v);
int dif = d[u] - d[v];
info a, b;
for (int i = lg; i >= 0; i--) {
if ((dif >> i) & 1) {
a = merge(a, ans[i][u]);
u = up[i][u];
}
}
if (u == v) {
a = merge(a, ans[0][u]);
} else {
for (int i = lg; i >= 0; i--) {
if (up[i][u] != up[i][v]) {
a = merge(a, ans[i][u]);
u = up[i][u];
b = merge(b, ans[i][v]);
v = up[i][v];
}
}
a = merge(a, ans[1][u]);
b = merge(b, ans[0][v]);
}
swap(b.minPrefL, b.minPrefR);
swap(b.maxPrefL, b.maxPrefR);
info res = merge(a, b);
if (res.minSeg <= x && x <= res.maxSeg) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
}
int main() {
int tests;
cin >> tests;
while (tests--) {
solve();
}
}