QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485630 | #6633. Exam Requirements | ucup-team1525 | ML | 484ms | 495576kb | C++17 | 3.3kb | 2024-07-20 21:48:13 | 2024-07-20 21:48:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5,T=1.5e7;
int n,m;
struct Int{
int l,r;
Int(int l=0,int r=0):l(l),r(r){}
}a[N+5];
int xs,x[N*2+5];
struct Re{
int x,y;
Re(int x=0,int y=0):x(x),y(y){}
}b[N+5];
struct SAT2{
int tot;
vector<int> e[T+5];
int trl[N*8+5],trr[N*8+5];
#define lc id<<1
#define rc id<<1|1
void adde(int u,int v){
e[u].push_back(v);
// printf("%d %d\n",u,v);
}
void addex(int u,int cu,int v,int cv){
e[u<<1|cu].push_back(v<<1|cv);
e[v<<1|(cv^1)].push_back(u<<1|(cu^1));
// printf("%d %d\n",u<<1|cu,v<<1|cv);
// printf("%d %d\n",v<<1|(cv^1),u<<1|(cu^1));
}
void build(int l,int r,int id){
trl[id]=trr[id]=++tot;
if(l==r) return;
int mid=l+r>>1;
build(l,mid,lc);
build(mid+1,r,rc);
}
void init(int n){
for(int i=1;i<=tot*2+1;i++)
e[i].clear();
tot=n;
build(1,xs,1);
}
void cover(int l,int r,int st,int en,int u,int id){
if(st<=l&&en>=r){
++tot;
addex(u,1,trr[id],0);
addex(u,1,tot,1);
addex(trr[id],1,tot,1);
trr[id]=tot;
return;
}
int mid=l+r>>1;
if(st<=mid) cover(l,mid,st,en,u,lc);
if(en>mid) cover(mid+1,r,st,en,u,rc);
}
void build2(int l,int r,int id){
if(l==r) return;
int mid=l+r>>1;
build2(l,mid,lc);
build2(mid+1,r,rc);
addex(trr[lc],1,trl[id],1);
addex(trr[rc],1,trl[id],1);
}
bool vis[T+5],in[T+5];
int st[T+5],ss;
int dfn[T+5],low[T+5],dfns;
int bl[T+5],cnt;
void dfs(int u){
vis[u]=1;
dfn[u]=low[u]=++dfns;
in[u]=1; st[++ss]=u;
for(auto v:e[u]){
if(!vis[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
cnt++;
while(st[ss]!=u){
bl[st[ss]]=cnt;
in[st[ss]]=0;
ss--;
}
bl[u]=cnt; in[u]=0; ss--;
}
}
bool work(){
assert(tot*2<=T);
ss=0; dfns=0; cnt=0;
for(int i=2;i<=tot*2+1;i++){
vis[i]=in[i]=dfn[i]=low[i]=bl[i]=0;
}
for(int i=2;i<=tot*2+1;i++)
if(!vis[i]) dfs(i);
for(int i=1;i<=tot;i++)
if(bl[i<<1|1]==bl[i<<1]) return 0;
return 1;
}
}S;
void solve(){
scanf("%d %d",&n,&m);
xs=0;
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].l,&a[i].r);
x[++xs]=a[i].l; x[++xs]=a[i].r+1;
}
for(int i=1;i<=m;i++)
scanf("%d %d",&b[i].x,&b[i].y);
sort(x+1,x+1+xs);
xs=unique(x+1,x+1+xs)-x-1;
// for(int i=1;i<=xs;i++)
// printf("%d ",x[i]);
// puts("");
S.init(n);
for(int i=1;i<=n;i++){
a[i].l=lower_bound(x+1,x+1+xs,a[i].l)-x;
a[i].r=lower_bound(x+1,x+1+xs,a[i].r+1)-x-1;
// printf("%d %d\n",a[i].l,a[i].r);
S.cover(1,xs,a[i].l,a[i].r,i,1);
}
S.build2(1,xs,1);
for(int i=1;i<=m;i++)
S.addex(b[i].x,0,b[i].y,1);
puts(S.work()?"YES":"NO");
}
int main(){
int t; scanf("%d",&t);
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 52ms
memory: 373732kb
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: 351ms
memory: 440040kb
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: 341ms
memory: 436016kb
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: 365ms
memory: 439960kb
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: 341ms
memory: 437976kb
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: 323ms
memory: 438012kb
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: 409ms
memory: 457732kb
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: 413ms
memory: 455692kb
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: 411ms
memory: 455780kb
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: 385ms
memory: 451572kb
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: 411ms
memory: 453688kb
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: 63ms
memory: 375956kb
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: 145ms
memory: 379332kb
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: 104ms
memory: 373272kb
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: 484ms
memory: 495256kb
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: 467ms
memory: 495576kb
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: -100
Memory Limit Exceeded
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