QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#128343#6633. Exam RequirementsKaphIAC ✓204ms196188kbC++142.4kb2023-07-20 21:33:362023-07-20 21:33:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 21:33:38]
  • 评测
  • 测评结果:AC
  • 用时:204ms
  • 内存:196188kb
  • [2023-07-20 21:33:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,m,pcnt,df[N*60],lw[N*60],dfn,is[N*60],st[N*60],nu[N*60],pos[N<<2],tp,cnt;
vector<int>E[N*60];
struct P{int l,r,id;}p[N];
bool cmp1(P a,P b){return a.l<b.l;}
void Rd(int &x){
	x=0;
	char c=getchar();
	while(!isdigit(c))c=getchar();
	do {x=(x<<1)+(x<<3)+(c^48);}while(isdigit(c=getchar()));
}
void edge_Add(int p,int z,int y,int c,int l,int r){
	if(l<=z&&y<=r){
//		printf("__%d %d    %d %d\n",p,pos[c],z,y);
		E[p<<1].push_back(pos[c]<<1|1);
		E[pos[c]<<1].push_back(p<<1|1);
		return;
	}
	int mid=(z+y)>>1;
	if(l<=mid)edge_Add(p,z,mid,c<<1,l,r);
	if(r>mid)edge_Add(p,mid+1,y,c<<1|1,l,r);
}
void dfs(int x){
	df[x]=lw[x]=++dfn;
	st[++tp]=x,is[x]=1;
	for(auto to:E[x]){
		if(!df[to]){
			dfs(to);
			lw[x]=min(lw[to],lw[x]);
		}else if(is[to])lw[x]=min(lw[x],df[to]);
	}
	if(df[x]==lw[x]){
		++cnt;
		int y;
		do{
			y=st[tp--];
			is[y]=0;
			nu[y]=cnt;
		}while(y!=x);
	}
}
void Js(int z,int y,int c){
	if(z==y){
		pos[c]=p[z].id;
		return;
	}
	pos[c]=++pcnt;
	int mid=(z+y)>>1;
//	printf("___%d  %d %d\n",nc,l,r);
	E[pcnt<<1].clear(),E[pcnt<<1|1].clear();
	df[pcnt<<1]=df[pcnt<<1|1]=0;
	Js(z,mid,c<<1),Js(mid+1,y,c<<1|1);
	E[pos[c<<1]<<1].push_back(pos[c]<<1);
	E[pos[c<<1|1]<<1].push_back(pos[c]<<1);
	E[pos[c]<<1|1].push_back(pos[c<<1]<<1|1);
	E[pos[c]<<1|1].push_back(pos[c<<1|1]<<1|1);
}
void slv(){
	Rd(n),Rd(m);
	for(int i=1;i<=n;++i){
		Rd(p[i].l),Rd(p[i].r);
		p[i].id=i;
		E[i<<1].clear(),E[i<<1|1].clear();
		df[i<<1]=df[i<<1|1]=0;
	}
	pcnt=n;
	sort(p+1,p+n+1,cmp1);
	Js(1,n,1);
	for(int i=1;i<=n;++i){
		int l=i+1,r=n,rs=i;
		while(l<=r){
			int mid=(l+r)>>1;
			if(p[mid].l<=p[i].r){
				rs=mid;
				l=mid+1;
			}else r=mid-1;
		}
//		printf("          __%d     %d %d\n",p[i].id,i+1,rs);
		if(i+1<=rs)edge_Add(p[i].id,1,n,1,i+1,rs);
	}
//	puts("?????");
	for(int i=1;i<=m;++i){
		int x,y;
		Rd(x),Rd(y);
		E[x<<1|1].push_back(y<<1);
		E[y<<1|1].push_back(x<<1);
	}
	for(int i=1;i<=n;++i){
		if(!df[i<<1])dfs(i<<1);
		if(!df[i<<1|1])dfs(i<<1|1);
		if(nu[i<<1]==nu[i<<1|1]){
			puts("NO");
			return;
		}
	}
	puts("YES");
//	for(int i=1;i<=pcnt;++i){
//		for(auto x:E[i<<1])printf("%d %d\n",i<<1,x);
//		for(auto x:E[i<<1|1])printf("%d %d\n",i<<1|1,x);
//	}
}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d",&T);
	while(T--)slv();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 19ms
memory: 153252kb

input:

2
3 1
1 5
2 7
10 11
2 1
3 3
1 5
2 7
5 7
1 2
2 3
3 1

output:

YES
NO

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 89ms
memory: 175436kb

input:

1
100000 100000
15084647 15220430
217541056 217598054
222963701 223110976
71224450 71340221
320463268 320631387
334861459 334924668
328950591 329083669
178996498 178996584
428529461 428605033
405428435 405504132
197936687 197947412
9058562 9190197
169407597 169474101
297518153 297590927
31471874 316...

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 0
Accepted
time: 103ms
memory: 172668kb

input:

1
100000 100000
14748507 14846251
125029948 125054609
463293218 463377641
198157217 198174486
61816219 61983451
43817835 43922214
146858750 146954988
30320405 30474901
19982332 20115324
118096811 118227915
446543803 446714206
334272499 334330640
334038396 334098710
142811467 142826092
343928730 3441...

output:

YES

result:

ok single line: 'YES'

Test #4:

score: 0
Accepted
time: 100ms
memory: 173096kb

input:

1
100000 100000
14378753 14427960
285902694 286019349
63076522 63199196
123034896 123091554
180956618 180971192
104893331 105077844
42717572 42770533
300075985 300247179
24213843 24240797
183255507 183392441
49921960 50077350
425570312 425743586
159753369 159916921
92930583 93006150
17541601 1766290...

output:

YES

result:

ok single line: 'YES'

Test #5:

score: 0
Accepted
time: 104ms
memory: 172452kb

input:

1
100000 100000
14008999 14009669
95199087 95219736
14436179 14597104
47912575 48008622
300097017 300106580
314204474 314321474
438388394 438398078
421595918 421783810
28445354 28554270
396649850 396832967
301347764 301488141
17056125 17196885
485280342 485399485
43049699 43186208
190966472 19098875...

output:

YES

result:

ok single line: 'YES'

Test #6:

score: 0
Accepted
time: 82ms
memory: 175888kb

input:

1
100000 100000
13605631 13735266
306114981 306163955
473109270 473261902
418782813 418868140
297212864 297253645
375822737 375911188
60621526 60621849
313499877 313647461
297219858 297394925
462722513 462902236
259120962 259259635
226014167 226123040
323655842 323840004
97994617 98082806
225359358 ...

output:

NO

result:

ok single line: 'NO'

Test #7:

score: 0
Accepted
time: 117ms
memory: 177164kb

input:

1
100000 100000
12378720 13625648
465814237 466616175
208691613 209863741
487589042 488474978
34489188 35271208
388644733 390469725
295170077 296291628
26123414 27676512
312050690 313755540
489093309 489538591
237262253 237973586
236118231 236780639
322598076 322794715
218797919 220330870
88459847 8...

output:

NO

result:

ok single line: 'NO'

Test #8:

score: 0
Accepted
time: 125ms
memory: 174480kb

input:

1
100000 100000
12025773 12899766
251831056 252958999
302794200 304237851
15424265 15656468
118197510 119570581
273660669 274814313
324357744 325209060
260709334 261019986
109892881 109901422
378006845 378110922
239114713 240200555
98023753 98835157
164309315 166050125
366410134 367688305
2150887 32...

output:

YES

result:

ok single line: 'YES'

Test #9:

score: 0
Accepted
time: 122ms
memory: 174128kb

input:

1
100000 100000
11672826 13497531
37847875 38695470
396896787 397288314
41329488 41514311
46702185 46736307
158676605 159765254
10679058 11260139
495295254 496293460
405805072 407370951
266920381 268613253
240967173 242427524
302795628 303149675
161224201 161255535
15952349 17582093
71045574 7273405...

output:

YES

result:

ok single line: 'YES'

Test #10:

score: 0
Accepted
time: 103ms
memory: 176568kb

input:

1
100000 100000
11319879 12165296
321934694 322501941
148133021 148796071
67234711 67372154
473276860 474508386
43692541 44109842
39866725 40783924
231811174 233496934
203647263 205446833
155833917 156579231
87615986 88844493
9497503 10000546
158139087 158390945
8360917 9735881
139940261 141601411
4...

output:

NO

result:

ok single line: 'NO'

Test #11:

score: 0
Accepted
time: 126ms
memory: 176440kb

input:

1
100000 100000
10950125 12051005
477581440 479154681
94266678 95909979
490182390 490895222
94347259 95525774
101284037 102455472
432053547 433727469
8722754 9737212
209620774 210562306
217508613 219120110
344267790 344951284
100795316 101617492
485408060 487219509
113683680 115563586
311623132 3122...

output:

YES

result:

ok single line: 'YES'

Test #12:

score: 0
Accepted
time: 25ms
memory: 154120kb

input:

10
1000 0
9084548 212659299
752049685 757793200
161999637 297780621
159218899 511613241
227411331 728832104
27428018 66692999
70254106 230710848
142218079 695911798
706863260 786626002
164254194 896730741
106307919 803778907
251793390 439950319
141699718 573753059
659066161 997295279
269040766 43188...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

result:

ok 10 lines

Test #13:

score: 0
Accepted
time: 45ms
memory: 154720kb

input:

10
10000 10000
8076128 8101663
29809420 29847609
370721525 370740253
892411542 892413288
747565478 747585274
5739499 5751302
227883289 227888911
696243800 696274475
209086262 209139782
153701675 153740284
794914 801208
712815424 712841626
488108468 488120604
546898456 546921288
517871533 517891373
1...

output:

YES
YES
NO
YES
YES
NO
YES
NO
YES
NO

result:

ok 10 lines

Test #14:

score: 0
Accepted
time: 25ms
memory: 153396kb

input:

100
691 691
508569640 508673802
208642094 208647922
28027525 28893278
215521571 216082768
432101881 432674036
287707806 288112166
757429741 757751727
729675214 730370857
359025437 359615838
697602408 698131276
443239285 444206285
186833263 187588090
357750289 357756701
552823963 552982349
527211763 ...

output:

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

result:

ok 100 lines

Test #15:

score: 0
Accepted
time: 114ms
memory: 180672kb

input:

1
50000 50000
235239015 627380255
144730978 542058842
550305498 565415835
328800870 680798359
385148497 675077021
362103943 863384846
59798050 589436710
113699937 487373907
557941848 790625291
60531465 592567224
41157560 245376586
825839343 875678662
159266647 695027240
319681713 822890545
247698126...

output:

NO

result:

ok single line: 'NO'

Test #16:

score: 0
Accepted
time: 118ms
memory: 181052kb

input:

1
50000 50000
626892852 633391382
332519095 895980171
583401233 961674476
352795837 693969388
30261670 447241929
226651863 602336203
583872139 849355310
79235608 858959672
78521707 943110748
724798770 952348869
424887625 958660184
703187100 863080259
555964295 685361175
390557968 397742944
529306351...

output:

NO

result:

ok single line: 'NO'

Test #17:

score: 0
Accepted
time: 184ms
memory: 188484kb

input:

1
100000 100000
611316630 629811740
91996695 793205603
205568177 975572692
476141394 984340236
739813611 910022525
212513275 370043741
310441153 445307964
319058023 346679908
670565549 934504580
566150142 993981165
932880384 935485719
680278897 980699546
244485251 927396846
322480796 833496991
34107...

output:

YES

result:

ok single line: 'YES'

Test #18:

score: 0
Accepted
time: 188ms
memory: 189356kb

input:

1
100000 100000
610946876 857807203
599281597 900917088
427496349 598338428
123875625 401019073
847949514 858954010
442677409 578978884
824577876 988838433
63366721 968387841
306867511 438548091
59515861 703179972
536258541 701410706
71997359 819298030
69824224 802640084
4101933 272599912
14689805 7...

output:

YES

result:

ok single line: 'YES'

Test #19:

score: 0
Accepted
time: 202ms
memory: 190716kb

input:

1
100000 100000
85802666 610577122
405357591 562353834
26903653 991108679
263411014 325896752
638392856 978094409
525357896 640430380
338714599 384885255
590095774 660191772
942591602 943169473
272534204 692726155
139636698 467335693
163295172 810833516
530399675 895163197
174706875 222719028
688302...

output:

NO

result:

ok single line: 'NO'

Test #20:

score: 0
Accepted
time: 183ms
memory: 188912kb

input:

1
100000 100000
31322880 610190561
373973574 896107801
482202027 913667658
92579172 149746887
638456885 716565783
25801083 640083865
143931232 778608280
96995720 266977967
5352786 562939706
662173707 686213373
905911158 993954199
99239139 137258923
274071980 903372610
88515186 122828692
616047378 68...

output:

YES

result:

ok single line: 'YES'

Test #21:

score: 0
Accepted
time: 204ms
memory: 188744kb

input:

1
100000 100000
609736772 846942098
34228770 550298572
102865196 803515622
385311112 716970493
53642257 208238815
264397673 588024468
207490182 921529793
292147365 766125091
116583023 745435603
105530143 905781497
409578135 887604888
199435485 837707075
232998371 933911494
85482313 827653326
1178684...

output:

YES

result:

ok single line: 'YES'

Test #22:

score: 0
Accepted
time: 77ms
memory: 157772kb

input:

10
10000 10000
968433817 980345689
103557645 824564023
829074871 997250637
474151154 894114908
716734949 928511820
579435564 960645476
162817 170066
26989283 75787020
330896 456526
312609711 500901739
503200 539839
693994 864159
959375 1027512
482433434 698751890
138723658 154257942
1157115 1278976
...

output:

YES
NO
YES
YES
YES
YES
NO
NO
YES
YES

result:

ok 10 lines

Test #23:

score: 0
Accepted
time: 87ms
memory: 157576kb

input:

10
10000 10000
55889446 676543761
339486739 512854517
89914 263037
43940346 743378135
474800917 474989262
381945 551085
53729144 521064977
625461 772887
174165490 859237741
895977 913869
122582738 363347004
1002118 1119286
557598499 854847993
1187071 1271634
1342510 1377024
1428419 1571587
1729397 1...

output:

NO
YES
NO
NO
NO
NO
YES
NO
NO
YES

result:

ok 10 lines

Test #24:

score: 0
Accepted
time: 178ms
memory: 187192kb

input:

1
100000 100000
2825612 287187070
999993267 1000000000
94 854
155005964 287573137
9070 21537
26142 34796
44434 45874
56159 63808
991386787 993171553
220122482 731015713
69663 87780
617617555 933500337
169625859 372421698
305623688 808834660
596826732 937822295
100817 108696
649207508 659155127
12219...

output:

YES

result:

ok single line: 'YES'

Test #25:

score: 0
Accepted
time: 183ms
memory: 196188kb

input:

1
100000 100000
3092 15274
19530 26942
33337 41977
627434658 942568814
43029 56667
697630428 961374423
58104 73299
110856530 735851270
82074 88280
141181852 262918400
96630091 650451770
92264 103401
172238029 172249854
388421560 643850618
105442 124096
131664 143119
280179217 333440826
148798 166640...

output:

NO

result:

ok single line: 'NO'

Test #26:

score: 0
Accepted
time: 178ms
memory: 193916kb

input:

1
100000 100000
10871 20950
37967 48437
285223721 594034432
51008 69067
76789 94787
97482 101557
26805305 26817148
115032 116107
387548524 412427666
129659 148344
38643779 237102119
163617 172021
188640 192596
202853 209871
216178 233816
252619 269075
478290210 592268749
853248909 963217231
282903 2...

output:

NO

result:

ok single line: 'NO'

Test #27:

score: 0
Accepted
time: 176ms
memory: 191680kb

input:

1
100000 100000
12795 27793
28468 41752
806312932 872614132
43181 55491
64694 82276
97343 111737
653273873 653281920
121362 135600
152867 169975
170207 170720
68812492 780071607
824067587 981895206
55248817 646910393
33392751 277269763
398950075 812465043
179090 185948
819483157 819498645
144084780 ...

output:

NO

result:

ok single line: 'NO'

Test #28:

score: 0
Accepted
time: 184ms
memory: 187368kb

input:

1
100000 100000
10221 14469
186957342 298058745
18743 36956
92950555 865157656
126663217 672393942
401361439 435570046
32239890 128425695
48937043 392849449
145368241 160614779
239539699 794392360
10826180 366721956
39944 40064
59006 60530
23920020 444334151
92172706 705687920
298764881 317566859
17...

output:

YES

result:

ok single line: 'YES'