↵
Идея: [user:EJIC_B_KEDAX,2023-06-21], разработка: [user:molney,2023-06-21]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1843A]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
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()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Оценка задачи">↵
- Не решал [likes:A,option1]↵
- Хорошая задача [likes:A,option2]↵
- Средняя задача [likes:A,option3]↵
- Плохая задача [likes:A,option4]↵
</spoiler>↵
↵
[problem:1843B]↵
↵
Идея: [user:EJIC_B_KEDAX,2023-06-21], разработка: [user:molney,2023-06-21]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1843B]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
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)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Оценка задачи">↵
- Не решал [likes:B,option1]↵
- Хорошая задача [likes:B,option2]↵
- Средняя задача [likes:B,option3]↵
- Плохая задача [likes:B,option4]↵
</spoiler>↵
↵
[problem:1843C]↵
↵
Идея: [user:Sokol080808,2023-06-21], разработка: [user:molney,2023-06-21]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1843C]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
s = 0↵
while n >= 1:↵
s += n↵
n //= 2↵
print(s)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Оценка задачи">↵
- Не решал [likes:C,option1]↵
- Хорошая задача [likes:C,option2]↵
- Средняя задача [likes:C,option3]↵
- Плохая задача [likes:C,option4]↵
</spoiler>↵
↵
[problem:1843D]↵
↵
Идея: [user:EJIC_B_KEDAX,2023-06-21], разработка: [user:Vladosiya,2023-06-21]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1843D]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Оценка задачи">↵
- Не решал [likes:D,option1]↵
- Хорошая задача [likes:D,option2]↵
- Средняя задача [likes:D,option3]↵
- Плохая задача [likes:D,option4]↵
</spoiler>↵
↵
[problem:1843E]↵
↵
Идея: [user:meowcneil,2023-06-21], разработка: [user:meowcneil,2023-06-21]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1843E]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
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()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Оценка задачи">↵
- Не решал [likes:E,option1]↵
- Хорошая задача [likes:E,option2]↵
- Средняя задача [likes:E,option3]↵
- Плохая задача [likes:E,option4]↵
</spoiler>↵
↵
[problem:1843F1]↵
↵
Идея: [user:EJIC_B_KEDAX,2023-06-21], разработка: [user:Sokol080808,2023-06-21]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1843F1]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
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()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Оценка задачи">↵
- Не решал [likes:F1,option1]↵
- Хорошая задача [likes:F1,option2]↵
- Средняя задача [likes:F1,option3]↵
- Плохая задача [likes:F1,option4]↵
</spoiler>↵
↵
[problem:1843F2]↵
↵
Идея: [user:EJIC_B_KEDAX,2023-06-21], разработка: [user:Sokol080808,2023-06-21]↵
↵
<spoiler summary="Разбор">↵
[tutorial:1843F2]↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
~~~~~↵
#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();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Оценка задачи">↵
- Не решал [likes:F2,option1]↵
- Хорошая задача [likes:F2,option2]↵
- Средняя задача [likes:F2,option3]↵
- Плохая задача [likes:F2,option4]↵
</spoiler>↵
↵
