QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #467845 | #6671. Zadatak | PorNPtree | 0 | 28ms | 35804kb | C++17 | 2.1kb | 2024-07-08 17:49:30 | 2024-07-08 17:49:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, L = 16;
struct op {
int l, r, c;
long long sB, sW;
} p[N << 5];
int a[N], rt[N << 1], tot;
int newNode(int l, int r) {
++tot, p[tot].l = p[tot].r = p[tot].c = 0;
p[tot].sB = 0, p[tot].sW = 1ll * r * r - 1ll * (l - 1) * (l - 1);
return tot;
}
void up(int k, int l, int r) {
int mid = (l + r) >> 1;
if (!p[k].l) p[k].l = newNode(l, mid);
if (!p[k].r) p[k].r = newNode(mid + 1, r);
p[k].c = p[p[k].l].c ^ p[p[k].r].c;
p[k].sB = p[p[k].r].sB + (p[p[k].r].c ? p[p[k].l].sW : p[p[k].l].sB);
p[k].sW = p[p[k].r].sW + (p[p[k].r].c ? p[p[k].l].sW : p[p[k].l].sB);
}
void modify(int &k, int l, int r, int x) {
if (!k) k = newNode(l, r);
if (l == r) {
p[k].sB = l + l - 1, p[k].sW = 0, p[k].c = 1;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) modify(p[k].l, l, mid, x);
else modify(p[k].r, mid + 1, r, x);
up(k, l, r);
}
long long res;
int merge(int x, int y, int l, int r, int c1, int c2) {
if (!x && !y) {
if (c1 && c2) res += 1ll * r * r - 1ll * (l - 1) * (l - 1);
return 0;
}
if (!x) {
if (c1) res += !c2 ? p[y].sB : p[y].sW;
return y;
}
if (!y) {
if (c2) res += !c1 ? p[x].sB : p[x].sW;
return x;
}
if (l == r) {
if ((p[x].c ^ c1) && (p[y].c ^ c2)) res += l + l - 1;
p[x].c ^= p[y].c;
if (p[y].c) swap(p[x].sB, p[x].sW);
return x;
}
int mid = (l + r) >> 1;
p[x].r = merge(p[x].r, p[y].r, mid + 1, r, c1, c2);
p[x].l = merge(p[x].l, p[y].l, l, mid, c1 ^ p[p[x].r].c ^ p[p[y].r].c, c2 ^ p[p[y].r].c);
up(x, l, r);
return x;
}
signed main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] >>= 1;
for (int i = 1; i <= n; ++i) modify(rt[i], 1, L, a[i]);
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
res = 0;
rt[n + i] = merge(rt[x], rt[y], 1, L, 0, 0);
printf("%lld\n", res << 2);
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 7944kb
input:
5000 217378 945562 533764 323494 69148 240722 205370 463122 552700 31800 616898 678076 893816 258468 34822 905360 967562 731346 340940 584418 684926 785402 107584 995542 363278 255302 196912 870994 329464 338390 154870 977540 65120 130388 350020 239660 553428 710306 385138 633274 841672 740778 17929...
output:
1024 1024 0 1024 0 0 776 1024 0 1024 1024 1024 1024 0 1024 0 0 776 0 1024 0 1024 0 0 0 776 0 0 1024 1024 0 0 776 1024 0 1024 1024 1024 0 1024 0 1024 1024 0 1024 0 1024 0 1024 1024 0 1024 1024 1024 0 0 0 776 0 776 0 776 1024 0 1024 1024 1024 0 1024 0 1024 1024 0 0 776 0 0 704 0 704 0 704 0 0 1024 102...
result:
wrong answer 1st lines differ - expected: '359872811236', found: '1024'
Subtask #2:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 28ms
memory: 35000kb
input:
100000 590812 862538 815196 397712 773198 172122 270600 609324 841858 4868 597128 216378 982576 385590 842010 55844 671758 885088 577804 194248 229770 859754 274744 678176 607974 791062 607192 210234 863164 619708 804538 430978 237704 10512 840374 843732 875326 255462 970338 898540 925508 661464 413...
output:
1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0 1024 0...
result:
wrong answer 1st lines differ - expected: '349058819344', found: '1024'
Subtask #3:
score: 0
Wrong Answer
Test #40:
score: 0
Wrong Answer
time: 22ms
memory: 35804kb
input:
65536 131908 883754 813278 197778 704074 981802 297078 903698 485360 496064 726120 251990 462786 129558 704500 920556 903884 454552 949354 328526 921462 975888 780002 276668 675308 49774 83014 136308 679916 42174 151084 358830 284218 259680 65684 526980 516764 200170 265060 294150 128046 658864 2984...
output:
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 ...
result:
wrong answer 1st lines differ - expected: '17399720464', found: '1024'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%