QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#400226 | #6671. Zadatak | nvujica | 0 | 185ms | 190480kb | C++14 | 2.6kb | 2024-04-27 05:41:59 | 2024-04-27 05:41:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 2e5 + 10, off = 1 << 20, maxcnt = 1e7;
int n, cnt;
set <int> s[maxn];
ll tour[maxcnt];
int prop[maxcnt];
int l[maxcnt];
int r[maxcnt];
int root[maxn];
vector <int> v;
void push(int x, int lo, int hi){
if(x >= off || prop[x] == 0) return;
int mid = (lo + hi) / 2;
prop[x] = 0;
tour[l[x]] = (mid - 1)*(mid - 1) - max(0, lo - 1)*(lo - 1) - tour[l[x]];
tour[r[x]] = (hi - 1)*(hi - 1) - (mid - 1)*(mid - 1) - tour[r[x]];
prop[l[x]] ^= 1;
prop[r[x]] ^= 1;
}
void update(int x, int lo, int hi, int rig){
// cout << x << ' ' << lo << ' ' << hi << ' ' << rig << ' ' << tour[x] << endl;
if(l[x] == 0){
cnt++;
l[x] = cnt;
cnt++;
r[x] = cnt;
}
push(x, lo, hi);
if(lo >= rig) return;
if(hi <= rig){
tour[x] = (hi - 1)*(hi - 1) - max(0, lo - 1)*(lo - 1) - tour[x];
prop[x] ^= 1;
return;
}
int mid = (lo + hi) / 2;
update(l[x], lo, mid, rig);
update(r[x], mid, hi, rig);
tour[x] = tour[l[x]] + tour[r[x]];
}
ll query(int x, int lo, int hi, int lef, int rig){
if(l[x] == 0){
cnt++;
l[x] = cnt;
cnt++;
r[x] = cnt;
}
push(x, lo, hi);
if(hi <= lef || lo >= rig) return 0;
if(lef <= lo && hi <= rig) return tour[x];
int mid = (lo + hi) / 2;
return query(l[x], lo, mid, lef, rig) + query(r[x], mid, hi, lef, rig);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
int a;
cin >> a;
a /= 2;
cnt++;
root[i] = cnt;
s[i].insert(a);
update(root[i], 0, off, a + 1);
}
for(int i = 1; i <= n - 1; i++){
int a, b;
cin >> a >> b;
if(s[b].size() > s[a].size()) swap(a, b);
v.clear();
v.push_back(0);
auto it = s[b].begin();
while(it != s[b].end()){
v.push_back(*it);
it++;
}
s[b].clear();
ll ans = 0;
// cout << a << ' ' << b << endl;
for(int j = v.size() - 1; j >= 1; j -= 2){
int q = query(root[a], 0, off, v[j - 1], v[j] + 1);
// cout << n + i << ' ' << v[j - 1] << ' ' << v[j] << ' ' << q << endl;
ans += q;
}
// cout << tour[1] << endl;
for(int j = 0; j < v.size(); j++){
if(s[a].find(v[j]) == s[a].end()) s[a].insert(v[j]);
else s[a].erase(v[j]);
update(root[a], 0, off, v[j] + 1);
// cout << v[j] << ' ' << "tour[1]: " << tour[1] << endl;
}
root[n + i] = root[a];
swap(s[n + i], s[a]);
cout << ans * 4 << "\n";
}
// cout << root[7] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 24ms
memory: 38372kb
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:
-904441628 -2949456624 -7035463888 -6468529776 6383832484 0 5053706852 -5471172572 0 3345046724 1969285636 3521841552 2322801664 -6808611776 -4096893952 0 942723908 6740758016 -5941125248 -8276270832 0 -1665810780 4810115772 4250085956 8095135860 -1782173968 9606758984 -3447637352 -1925738396 233833...
result:
wrong answer 1st lines differ - expected: '359872811236', found: '-904441628'
Subtask #2:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 185ms
memory: 190480kb
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:
5461435664 -5465105672 -1572860 -8159275508 -524284 -4733755484 6927030936 132011464 0 -4137401692 -4740692072 -4392766840 4484359860 -7139799400 6936588 -575029480 5408688356 -2829541564 -6785633652 -2960449368 4989855060 289788548 41948772 -756811840 1751607232 -756811840 -5863999920 6741160040 48...
result:
wrong answer 1st lines differ - expected: '349058819344', found: '5461435664'
Subtask #3:
score: 0
Runtime Error
Test #40:
score: 0
Runtime Error
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:
219851280 -524284 -2496008860 2355992164 -4943838976 -524284 4294705156 -1895956336 -1572860 -1048572 7278627428 -1048572 0 6891324196 0 5646505872 4294180868 4314387856 4294180868 1537326864 -784091068 3187382756 -1572860 0 -4328140028 1071513604 5164975104 -1048572 758272036 -1380264732 -1572860 -...
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%