QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#400226#6671. Zadataknvujica0 185ms190480kbC++142.6kb2024-04-27 05:41:592024-04-27 05:41:59

Judging History

你现在查看的是最新测评结果

  • [2024-04-27 05:41:59]
  • 评测
  • 测评结果:0
  • 用时:185ms
  • 内存:190480kb
  • [2024-04-27 05:41:59]
  • 提交

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%