QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#147523#6633. Exam Requirementsqzez#WA 230ms267388kbC++142.7kb2023-08-23 12:01:262023-08-25 01:37:58

Judging History

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

  • [2023-08-25 01:37:58]
  • 评测
  • 测评结果:WA
  • 用时:230ms
  • 内存:267388kb
  • [2023-08-23 12:01:26]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e5+5,M=N*40+5,K=14348907+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
int n,m,A[N],B[N];
vector<pii> Id[N];
vector<int> S[M];
int Ct,SCC;
void con(int x,int y){S[x].emplace_back(y);}
pair<int,int*> Ns[N];int Nh;
namespace CT{
	int CC,L[M],R[M],I1[M],I2[M];
	void Cl(){for(int i=1;i<=CC;i++) L[i]=R[i]=I1[i]=I2[i]=0;CC=0;}
	void CP(int &v){L[++CC]=L[v];R[CC]=R[v];I1[CC]=++Ct;I2[CC]=++Ct;if(v) con(I1[CC],I1[v]),con(I2[v],I2[CC]);v=CC;}
	void add(int x,int id,int &v,int l=1,int r=Nh){
		if(!v) CP(v);con(I1[v],id+n);con(id,I2[v]);if(l==r) return;
		int m=l+r>>1;x<=m?add(x,id,L[v],l,m):add(x,id,R[v],m+1,r);
	}
	void qry(int x,int y,int id,int v,int l=1,int r=Nh){
		if(!v) return;
		if(x<=l&&r<=y) return con(id,I1[v]),con(I2[v],id+n);int m=l+r>>1;
		x<=m&&(qry(x,y,id,L[v],l,m),0);y>m&&(qry(x,y,id,R[v],m+1,r),0);
	}
}
int scc[M];
namespace Tarjan{
	int dfn[M],low[M],dh,st[M],sh,vis[M];
	void Cl(){for(int i=1;i<=Ct;i++) dfn[i]=low[i]=vis[i]=st[i]=scc[i]=0;dh=sh=0;}
	void Tarjan(int x){
		dfn[x]=low[x]=++dh;st[++sh]=x;vis[x]=1;for(int i:S[x]){
			if(!dfn[i]) Tarjan(i),low[x]=min(low[x],low[i]);else if(vis[i]) low[x]=min(low[x],dfn[i]);
		}if(dfn[x]<=low[x]) {SCC++;while(st[sh+1]^x) vis[st[sh]]=0,scc[st[sh--]]=SCC;}
	}
	void BD(){for(int i=1;i<=Ct;i++) if(!dfn[i]) Tarjan(i);}
}
int Ro[N];
void Solve(){
	int i,j;
	for(i=1;i<=Nh;i++) Id[i].clear();Nh=0;
	for(i=1;i<=Ct;i++) S[i].clear();Tarjan::Cl();Ct=SCC=0;CT::Cl();
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d%d",&A[i],&B[i]),Ns[++Nh]=make_pair(A[i],&A[i]),Ns[++Nh]=make_pair(B[i],&B[i]);
	sort(Ns+1,Ns+Nh+1);for(i=1;i<=Nh;i++) *Ns[i].se=i;
	Ct=2*n;
	/*for(i=1;i<=Nh;i++){
		Ro[i]=Ro[i-1];
		for(auto j:Id[i]) CT::qry(j.fi,i,j.se,Ro[i]),CT::add(i,j.se,Ro[i]);
	}*/
	for(i=1;i<=n;i++) CT::add(B[i],i,Ro[0]);
	for(i=1;i<=n;i++) if(A[i]^B[i]) CT::qry(A[i],B[i]-1,i,Ro[0]);
	while(m--){
		int x,y;scanf("%d%d",&x,&y);
		con(x+n,y);con(y+n,x);
	}
	Tarjan::BD();
	for(i=1;i<=n;i++) if(scc[i]==scc[i+n]){puts("NO");return;}
	puts("YES");
}
int main(){
	int t;
	scanf("%d",&t);
	// t=1;                                                                                       
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 208748kb

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: 230ms
memory: 265728kb

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: 208ms
memory: 264536kb

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: 220ms
memory: 267388kb

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: 210ms
memory: 264560kb

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: 225ms
memory: 265780kb

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: -100
Wrong Answer
time: 220ms
memory: 263012kb

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:

YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'