QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#822848	#9905. 哈夫曼树	Flamire	100 ✓	1569ms	14736kb	C++17	1.5kb	2024-12-20 17:00:53	2024-12-20 17:00:54

Judging History

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

[2024-12-20 17:00:54]
评测

测评结果：100
用时：1569ms
内存：14736kb

查看

[2024-12-20 17:00:53]
提交

answer

#include <bits/stdc++.h>
#define ll long long
#define N 200011
#define pii pair<ll,ll>
#define s1 first
#define s2 second
using namespace std;
int n,q;ll a[N];
int fa[N],lc[N],rc[N];
multiset<pii> st;
int f(pii a,pii b)
{
	if(a.s2<=b.s1)return 0;
	return 1;
}
int C;
void calc(pii x,int w)
{
	auto it=st.lower_bound(x),itl=it,itr=it;
	if(it!=st.begin())
	{
		itl=it;--itl;
		C+=w*f(*itl,*it);
	}
	itr=it;++itr;
	if(itr!=st.end())C+=w*f(*it,*itr);
	if(itl!=it&&itr!=st.end())C-=w*f(*itl,*itr);
}
void ins(pii x)
{
	if(x.s1>x.s2)swap(x.s1,x.s2);
	st.insert(x);calc(x,1);
}
void del(pii x)
{
	if(x.s1>x.s2)swap(x.s1,x.s2);
	calc(x,-1);st.erase(st.find(x));
}
int h[N];
const int A=100;
void dfs(int u)
{
	if(u<=n){h[u]=0;return;}
	dfs(lc[u]);dfs(rc[u]);
	h[u]=max(h[lc[u]],h[rc[u]])+1;
}
int main()
{
	scanf("%d%d",&n,&q);int rt=0;
	for(int i=1;i<=n;++i)scanf("%lld",a+i);
	for(int i=n+1;i<2*n;++i)scanf("%d%d",lc+i,rc+i),fa[lc[i]]=fa[rc[i]]=i;
	for(int i=1;i<2*n;++i)if(!fa[i])rt=i;
	dfs(rt);
	if(h[rt]>=A){while(q--)printf("NO\n");return 0;}
	for(int i=1;i<=n;++i)
	{
		int u=fa[i];
		while(u)a[u]+=a[i],u=fa[u];
	}
	for(int i=n+1;i<2*n;++i)ins(pii(a[lc[i]],a[rc[i]]));
	printf(C?"NO\n":"YES\n");
	for(int _=1;_<q;++_)
	{
		int p;ll v;scanf("%d%lld",&p,&v);v-=a[p];
		while(p)
		{
			if(fa[p])del(pii(a[lc[fa[p]]],a[rc[fa[p]]]));
			a[p]+=v;
			if(fa[p])ins(pii(a[lc[fa[p]]],a[rc[fa[p]]]));
			p=fa[p];
		}
		printf(C?"NO\n":"YES\n");
	}
	fclose(stdin);fclose(stdout);return 0;
}

Source code, Language: C++17

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 30

Accepted

Test #1:

score: 30

Accepted

time: 1ms

memory: 5812kb

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: 7860kb

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: 0ms

memory: 7912kb

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: 1ms

memory: 5872kb

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: 30

Accepted

time: 1ms

memory: 5816kb

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:

ok 1000 token(s): yes count is 199, no count is 801

Test #6:

score: 30

Accepted

time: 1ms

memory: 5944kb

input:

8 1000
172480280419267 212072146993988 23147786306112 161006134777989 37963466387491 50018942108886 18649770050090 50499101532214
7 3
2 1
5 8
9 6
12 11
4 13
10 14
5 57899673021751
7 22087918088240
1 236990257757485
3 21994370580136
7 26427284121647
8 54391900162086
7 27709763713585
6 59631479929866
...

output:

NO
NO
NO
YES
YES
YES
YES
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
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
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
YES...

result:

ok 1000 token(s): yes count is 119, no count is 881

Test #7:

score: 30

Accepted

time: 0ms

memory: 5876kb

input:

6 1000
20326746134626 98517002313418 165556087937310 116347939244398 130872245741329 136674587230071
2 3
6 7
8 1
9 5
10 4
4 31902652070998
2 20697837065544
3 14389422108471
5 45879772826060
2 23505088168423
6 7588643182717
2 13873224035289
4 3462171437780
6 12963735380517
6 3348685354818
3 141429739...

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
YES
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 1000 token(s): yes count is 12, no count is 988

Test #8:

score: 30

Accepted

time: 4ms

memory: 5944kb

input:

72 1000
2 10946 610 987 139583862445 20365011074 5 1597 196418 377 267914296 44945570212853 956722026041 5702887 39088169 75025 27777890035288 12586269025 4181 1 53316291173 144 1548008755920 63245986 1 225851433717 6557470319842 832040 2504730781961 102334155 55 3 46368 7778742049 6765 165580141 72...

output:

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

result:

ok 1000 token(s): yes count is 598, no count is 402

Test #9:

score: 30

Accepted

time: 4ms

memory: 5944kb

input:

70 1000
31322671994689 1078810887856 579849 254672704401 136883 4713 4569916255830 11964196083506 19970 22963823428 157396387326 488813369 12341 1 61 1799 162 82003819900560 221480 5421023350 44076273 37 261 347373755513422 6430641 938216 71316908 687 7394279827673 302103276 2456284 32311 1745552683...

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 1000 token(s): yes count is 986, no count is 14

Test #10:

score: 30

Accepted

time: 4ms

memory: 5936kb

input:

1000 1000
696394773309 108383178182 819893348793 723784375461 931503257800 952660789032 100236017416 539829053718 209653090976 981815062655 964960614840 961643834067 369486282052 800646303984 387416608811 261777906950 172691588923 485971148690 453102872226 770561490733 375803723200 861225005889 1185...

output:

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
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
...

result:

ok 1000 token(s): yes count is 290, no count is 710

Test #11:

score: 30

Accepted

time: 2ms

memory: 5944kb

input:

1000 1000
328753409716 63174357177 116706499724 751756098545 913879475315 309225707947 610363994448 928602608183 298378305770 255654307269 444288397875 332511908079 297834684008 532592347055 268793918986 782156365515 316531786356 584037378094 809660826672 456709928147 277332 603219716866 60062165567...

output:

YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
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
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
...

result:

ok 1000 token(s): yes count is 124, no count is 876

Test #12:

score: 30

Accepted

time: 0ms

memory: 5960kb

input:

1000 1000
596779917266 859728384612 790999537569 946122172426 539615683280 616114813176 675147442971 523252967306 989540738771 880850130723 850501333358 858531013132 700803829612 642617589194 814265292894 799430766156 589454900606 735369030885 797404510621 602718454036 883696282103 974675349909 7793...

output:

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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 1000 token(s): yes count is 3, no count is 997

Test #13:

score: 30

Accepted

time: 6ms

memory: 5900kb

input:

1000 1000
12340874 29443 42 12492 139286 153819 53474891 4999 5513602 15 15542744701 367380 19381 1390668 27542397298 328751473 10398280 3528202605 126026926 21552 4031001 14293341319 140519268911 360904 1422 28 13089 32427234919 457240409937 17711545787 39539446 51 355784231 810175146335 916553144 ...

output:

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
YES
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
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
Y...

result:

ok 1000 token(s): yes count is 749, no count is 251

Test #14:

score: 30

Accepted

time: 3ms

memory: 5924kb

input:

1000 1000
19 27 18 26 41 49 29 27 46 24 43 25 50 4 17 25 15 15 4 33 24 35 10 7 27 3 39 43 36 28 29 5 20 5 42 43 33 17 11 26 43 21 38 31 12 33 48 33 14 29 48 49 15 37 16 4 16 44 25 45 41 17 37 49 32 40 9 12 8 22 2 24 9 21 14 16 34 45 47 25 28 16 26 7 11 42 26 29 35 32 34 44 11 30 20 47 13 6 41 19 37 ...

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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
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 468, no count is 532

Test #15:

score: 30

Accepted

time: 1ms

memory: 8004kb

input:

1000 1000
996069901379 940888328260 925342655682 923520191546 877076702411 855421610507 842224729549 837033687452 810175146335 792646717951 752993949814 717579080665 711089804069 708221643771 699280599587 697696794210 670880120082 641841749136 631447339331 619769332589 617930141820 586690159836 5636...

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 1000 token(s): yes count is 0, no count is 1000

Subtask #2:

score: 20

Accepted

Test #16:

score: 20

Accepted

time: 37ms

memory: 6648kb

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: 28ms

memory: 8564kb

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: 90ms

memory: 6724kb

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: 8104kb

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: 239ms

memory: 11220kb

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: 325ms

memory: 9620kb

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: 652ms

memory: 10204kb

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: 10ms

memory: 7656kb

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: 20

Accepted

Test #24:

score: 20

Accepted

time: 289ms

memory: 5880kb

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: 551ms

memory: 14352kb

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: 516ms

memory: 14736kb

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: 530ms

memory: 13976kb

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: 20

Accepted

time: 1569ms

memory: 14220kb

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...

result:

ok 100000 token(s): yes count is 350, no count is 99650

Test #29:

score: 20

Accepted

time: 21ms

memory: 9896kb

input:

100000 100000
9999834711 9998930249 9995255552 9993501823 9990418195 9989945168 9988551585 9988190213 9985354954 9985308095 9984359451 9982945279 9982266980 9981553307 9981304989 9979767996 9979737063 9978618141 9971036317 9967584170 9965984612 9962485753 9958389098 9952132366 9951200056 9948789025 ...

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 100000 token(s): yes count is 0, no count is 100000

Extra Test:

score: 0

Extra Test Passed