QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#821627	#9905. 哈夫曼树	Fesdrer	50	1670ms	31016kb	C++17	2.7kb	2024-12-19 17:00:23	2024-12-19 17:00:23

Judging History

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

[2024-12-19 17:00:23]
评测

测评结果：50
用时：1670ms
内存：31016kb

查看

[2024-12-19 17:00:23]
提交

answer

#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
const int N=1e5+5,M=80;
int n,q,mxdep,fa[N<<1],dep[N<<1],ls[N<<1],rs[N<<1];
long long val[N<<1],a[N];
multiset<pair<long long,long long>> s;
multiset<long long> sd[M+5];
int cnt;
inline bool check(pair<long long,long long> x,pair<long long,long long> y){
	return (y.second<x.first);
}
inline int cp(int x){
	return (ls[fa[x]]==x?rs[fa[x]]:ls[fa[x]]);
}
inline pair<long long,long long> get(int p){
	return {val[p],val[cp(p)]};
}
inline void erase(pair<long long,long long> x){
	// if(x.first<=x.second)	return;
	auto it=s.find(x);
	if(s.size()!=1){
		if(x==*s.begin())	cnt-=check(x,*++s.begin());
		else if(x==*s.rbegin())	cnt-=check(*--s.rbegin(),x);
		else{
			pair<long long,long long> l=*(--it);it++;
			pair<long long,long long> r=*(++it);it--;
			cnt-=check(l,x)+check(x,r)-check(l,r);
		}
	}
	s.erase(it);
}
inline void insert(pair<long long,long long> x){
	// if(x.first<=x.second)	return;
	auto it=s.insert(x);
	if(s.size()!=1){
		if(x==*s.begin())	cnt+=check(x,*++s.begin());
		else if(x==*s.rbegin())	cnt+=check(*--s.rbegin(),x);
		else{
			pair<long long,long long> l=*(--it);it++;
			pair<long long,long long> r=*(++it);
			cnt+=check(l,x)+check(x,r)-check(l,r);
		}
	}
}
inline void changeval(int p,long long v){
	sd[dep[p]].erase(sd[dep[p]].find(val[p])),sd[dep[p]].insert(v);
	if(dep[p]==1){val[p]=v;return;}
	pair<long long,long long> e1=get(p),e2=get(cp(p));
	val[p]=v;
	pair<long long,long long> i1=get(p),i2=get(cp(p));
	erase(e1),erase(e2),insert(i1),insert(i2);
}
inline void change(int p,long long v){
	changeval(p,v);
	while(p!=n*2-1)	p=fa[p],changeval(p,val[ls[p]]+val[rs[p]]);
}
inline bool solve(){
	for(int i=1;i<mxdep;i++) if(*sd[i].begin()<*(--sd[i+1].end()))	return 0;
	return cnt==0;
}
int main(){
	// freopen("ex_huffman4.in","r",stdin);
	// freopen("ex_huffman4.my","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	if(n==1){
		while(q--)	puts("YES");
		return 0;
	}
	for(int i=1;i<=n;i++)	cin>>a[i],val[i]=a[i];
	for(int i=n+1;i<n*2;i++){
		cin>>ls[i]>>rs[i];
		fa[ls[i]]=i,fa[rs[i]]=i,val[i]=val[ls[i]]+val[rs[i]];
	}
	dep[n*2-1]=1;
	mxdep=1;
	for(int i=n*2-1;i>=n+1;i--){
		dep[ls[i]]=dep[i]+1,dep[rs[i]]=dep[i]+1;
		mxdep=max(mxdep,dep[ls[i]]),mxdep=max(mxdep,dep[rs[i]]);
	}
	if(mxdep>M){
		while(q--)	puts("NO");
		return 0;
	}
	for(int i=1;i<=n*2-1;i++)	sd[dep[i]].insert(val[i]);
	for(int i=1;i<=n*2-2;i++)	insert(get(i));
	puts(solve()?"YES":"NO");
	q--;
	while(q--){
		int p;
		long long v;
		cin>>p>>v;
		change(p,v);
		puts(solve()?"YES":"NO");
	}
	return 0;
}

源文件, 语言: C++17

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 30

Accepted

time: 0ms

memory: 7668kb

input:

output:

YES
NO
YES
NO

result:

ok 4 token(s): yes count is 2, no count is 2

Test #2:

score: 30

Accepted

time: 0ms

memory: 7740kb

input:

8 5
5 3 4 2 2 6 5 5
1 8
4 5
10 3
11 9
7 2
6 13
14 12
7 3
6 8
4 2
2 5

output:

NO
YES
YES
YES
NO

result:

ok 5 token(s): yes count is 3, no count is 2

Test #3:

score: 30

Accepted

time: 2ms

memory: 7760kb

input:

5 1000
193989534544158 57483670601746 183281373434588 92196008024549 197513473286508
1 5
4 2
7 3
8 6
2 65545142774024
4 67957472319495
5 131478473459166
2 102185858570152
3 191441353035940
5 186000528093501
2 63201184033501
2 77481806092413
3 159789430863849
4 92773786021894
1 194598667478593
3 1458...

output:

YES
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
...

result:

ok 1000 token(s): yes count is 375, no count is 625

Test #4:

score: 30

Accepted

time: 0ms

memory: 7676kb

input:

7 1000
88159166205053 95998544558881 48231159865354 231786835189365 84291070100955 225941839972605 33315221625793
2 5
6 4
7 3
1 10
8 11
9 12
6 150843468162951
2 75759088055460
1 86133344610051
4 140694127444493
1 63070113756930
1 90150689680608
6 147790469610032
7 46561924657801
2 103953340734616
6 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 1000 token(s): yes count is 86, no count is 914

Test #5:

score: 0

Wrong Answer

time: 2ms

memory: 5760kb

input:

7 1000
5 6 7 3 2 5 5
4 7
3 5
1 2
10 6
8 9
12 11
5 2
5 1
5 1
1 2
3 2
5 1
5 2
6 3
4 2
4 1
2 1
5 1
5 1
5 1
7 1
1 2
5 1
5 1
6 3
6 3
5 1
2 2
7 2
7 1
7 1
2 2
1 2
4 2
4 1
1 1
3 1
5 1
2 2
2 2
4 1
2 1
7 2
6 1
2 1
6 2
5 2
1 1
1 1
6 3
7 2
6 3
4 1
1 1
5 1
2 2
7 2
5 1
4 2
5 2
7 2
7 1
4 1
3 2
3 2
1 1
7 2
5 2
1 1
...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

wrong answer expected YES, found NO [175th token]

Subtask #2:

score: 20

Accepted

Test #16:

score: 20

Accepted

time: 94ms

memory: 8212kb

input:

10000 10000
85117964119 41472951000 61693640396 66409648221 91978532661 62922448518 92497200794 43837348258 45577855926 38256001396 79446271832 95289903258 62510175551 97599809584 56162244722 87617641117 64010325734 56604859803 58544571483 40687963085 38627694508 64665875035 62273927372 73014847094 ...

output:

YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 10000 token(s): yes count is 1207, no count is 8793

Test #17:

score: 20

Accepted

time: 74ms

memory: 8360kb

input:

10000 10000
84900060848 62644704574 98718077349 98821154996 62378873948 84056095227 88175599645 82631986335 89400902292 62154382134 88902573868 60394670260 90463768093 55792148201 54981081426 88759069805 61152773490 92471234756 97882399939 60966664424 77983213922 86899012963 99014573954 61451810141 ...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 10000 token(s): yes count is 1, no count is 9999

Test #18:

score: 20

Accepted

time: 185ms

memory: 8208kb

input:

10000 10000
93919 1531126631 30535211 270124792 175 384 79432924528 57926141453 28 5497 3726 1802376440 193463181 493828 69230 574 52891249 4467144512 249874064 679 384407292 1656687680 6538 1702 531231 20166752330 15505 82 3284 4814 162 15208812 17569 809 5204 703838 3627957764 44761779 7256061080 ...

output:

YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 10000 token(s): yes count is 463, no count is 9537

Test #19:

score: 20

Accepted

time: 3ms

memory: 8020kb

input:

10000 10000
99806537703 99766194869 99292379197 99207104032 99114739849 98889965040 98714163547 98624741525 98537071301 98408984814 97981236991 97867856128 97728640101 97720014922 97379361440 97285651187 97111208501 97096802253 96643517597 96360376855 95783851225 95377161230 95072710034 94889685140 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 10000 token(s): yes count is 0, no count is 10000

Subtask #3:

score: 30

Accepted

Test #20:

score: 30

Accepted

time: 670ms

memory: 19476kb

input:

50000 50000
16394396247 17456058492 11358090355 13208121167 8612535629 2853817504 18100755237 18603321637 1618810635 7615832530 13631222424 7817630977 10963098997 19654927084 645638016 9352759139 17939720223 15106346489 14475376391 2122412099 15482023637 11224675857 15931143509 4240408932 1270948838...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 50000 token(s): yes count is 6146, no count is 43854

Test #21:

score: 30

Accepted

time: 815ms

memory: 19384kb

input:

50000 50000
16115874901 16018205653 14928961193 15204162048 13699373395 16820637318 16493035276 12317462119 12335280079 14846384661 17397129601 13936553564 14115670390 10273255127 15120549487 18610914980 11122287472 11331160875 18972429908 12783865866 14407025341 18691310891 11400735942 15689404271 ...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 50000 token(s): yes count is 97, no count is 49903

Test #22:

score: 30

Accepted

time: 1670ms

memory: 18368kb

input:

50000 50000
3993 223081374 1585900689 19301459402 43 928559 17 9528421232 1595336240 17039424626 8356250 531391708 1218 551210298 37104 110710 81842739 119946920 37855516 10200 438 2736 201 23 1438 378221115 23 81 8281519 4554 205450323 52777 10352 45646 15 116342579 4459504 31 19342289293 483194 76...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 50000 token(s): yes count is 448, no count is 49552

Test #23:

score: 30

Accepted

time: 6ms

memory: 7636kb

input:

50000 50000
19988593123 19987997685 19985224140 19980200906 19974260733 19973543573 19966775533 19962491364 19957673556 19951057741 19934887728 19924084943 19912519998 19910951955 19909656706 19908299113 19905363420 19903730114 19900763202 19883792717 19866579628 19863208341 19860493642 19841577977 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 50000 token(s): yes count is 0, no count is 50000

Subtask #4:

score: 0

Time Limit Exceeded

Test #24:

score: 20

Accepted

time: 790ms

memory: 5668kb

input:

70 100000
66748 126 1 91045172 3605661959574 274077743637349 147314183 8209537 740253 6920630855 25494 1377240316614 15756 6 108000 18118446805 169389361127761 29316262755 48 2643445763 5834083602536 3 9439745562111 29 3719 10 47434709561 11197815949 6018 325122336074 851181326345 1633739329 1527382...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 100000 token(s): yes count is 98093, no count is 1907

Test #25:

score: 20

Accepted

time: 1507ms

memory: 30976kb

input:

100000 100000
7549638646 8066727970 9672316362 9615802181 6376690689 416134043 5288164622 2316444041 8423663950 1806779510 3010692396 7782858557 4229348735 1361364214 9005774175 6382408188 8174082766 8406340542 8599848784 3178078732 1395839441 5310497981 6807939596 2743315129 3143071583 3636776799 5...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
...

result:

ok 100000 token(s): yes count is 14280, no count is 85720

Test #26:

score: 20

Accepted

time: 1487ms

memory: 30972kb

input:

100000 100000
872896800 2642237960 7854830770 2526006918 2460372877 6275745887 9542824270 2259554484 7939727171 5684426763 3142930947 4722146974 4449153152 6010317250 9601373467 1320115120 1554509921 9484729979 4623237659 8207960981 9918495458 5636697884 8103563399 2247522457 3949979832 5293808722 8...

output:

YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 100000 token(s): yes count is 13620, no count is 86380

Test #27:

score: 20

Accepted

time: 1269ms

memory: 31016kb

input:

100000 100000
7198797097 5435854448 9924139315 6509926805 6680038286 7582083493 8295697626 7987541001 6072017580 7487771114 7193879849 5761987728 8304525744 9604078001 6299845419 6733294485 9820196538 9587148702 5909774105 8852968034 9179846573 6366260329 7688429446 6297118602 7348639021 6888450227 ...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 100000 token(s): yes count is 33, no count is 99967

Test #28:

score: 0

Time Limit Exceeded

input:

100000 100000
4056837102 824104887 186 1311392 9313623872 8480 77121209 51422880 21389 15291 576956653 836 3456 7213630426 8779959870 273146 246 2205733 2579200972 36389 90998675 61 303221391 699293 10264244 6947232 2591 387 5853095 85 89 241 1603 704 2070710485 1762025505 8455788725 2962231 1657062...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...