QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#147523 | #6633. Exam Requirements | qzez# | WA | 230ms | 267388kb | C++14 | 2.7kb | 2023-08-23 12:01:26 | 2023-08-25 01:37:58 |
Judging History
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'