QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#223897 | #6633. Exam Requirements | Nerovix | ML | 43ms | 392692kb | C++14 | 4.1kb | 2023-10-22 20:10:12 | 2023-10-22 20:10:13 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define ll long long
#define db double
using namespace std;
const int mod=1e9+7;
const db pi=acos(-1);
const db eps=1e-9;
int add(int x,int y){
x+=y;
return x>=mod?x-mod:x;
}
void adto(int&x,int y){
x+=y;
x>=mod?x-=mod:0;
}
int mul(int x,int y){
return 1ll*x*y%mod;
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
const int maxn=100000+10,maxnode=maxn*80;
int n,m,e[maxn],s[maxn],a[maxn],b[maxn];
vector<int>v[maxnode],rv[maxnode];
void addedge(int a,int b){
assert(a);
assert(b);
v[a].pb(b);
rv[b].pb(a);
}
int ls[maxnode],rs[maxnode],id[maxnode];
int idt[maxn],idf[maxn];
int tcnt;
int idcnt;
pair<int,int>llsh[maxn];
void ins(int&i,int old,int l,int r,int p,int nodeid,int faid){
i=++tcnt;
ls[i]=ls[old];
rs[i]=rs[old];
id[i]=++idcnt;
if(old)addedge(id[i],id[old]);
if(faid)addedge(faid,id[i]);
if(l==r){
addedge(id[i],nodeid);
return;
}
int mid=l+r>>1;
if(p<=mid){
if(rs[i]){
addedge(id[i],id[rs[i]]);
}
ins(ls[i],ls[old],l,mid,p,nodeid,id[i]);
}
else{
if(ls[i]){
addedge(id[i],id[ls[i]]);
}
ins(rs[i],rs[old],mid+1,r,p,nodeid,id[i]);
}
return;
}
void taddedge(int i,int l,int r,int x,int y,int nodeid){
if(!i||y<x||r<x||y<l)return;
if(x<=l&&r<=y)return addedge(nodeid,id[i]),void();
int mid=l+r>>1;
if(x<=mid)taddedge(ls[i],l,mid,x,y,nodeid);
if(y>mid)taddedge(rs[i],mid+1,r,x,y,nodeid);
}
int rt[maxn<<1];
int col[maxnode];
int q[maxnode],t;
int vis[maxnode];
void dfs1(int x){
vis[x]=1;
for(int y:v[x]){
if(!vis[y])dfs1(y);
}
q[++t]=x;
}
void dfs2(int x,int c){
vis[x]=0;
col[x]=c;
for(int y:rv[x]){
if(vis[y])dfs2(y,c);
}
}
void kosaraju(){
for(int i=1;i<=idcnt;i++){
vis[i]=0;
col[i]=0;
}
t=0;
for(int i=1;i<=idcnt;i++){
if(!vis[i])dfs1(i);
}
// cerr<<t<<" "<<idcnt<<"\n";
assert(t==idcnt);
for(int i=idcnt;i;i--){
if(vis[q[i]])dfs2(q[i],q[i]);
}
}
void clearup(){
for(int i=1;i<=idcnt;i++){
v[i].clear();
rv[i].clear();
}
tcnt=idcnt=0;
}
void solve(){
static int lsh[maxn<<1];
int lt=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i]>>e[i];
lsh[++lt]=s[i];
lsh[++lt]=e[i];
}
sort(lsh+1,lsh+lt+1);
lt=unique(lsh+1,lsh+lt+1)-lsh-1;
vector<vector<int> >tmpv(lt+5);
for(int i=1;i<=n;i++){
s[i]=lower_bound(lsh+1,lsh+lt+1,s[i])-lsh;
e[i]=lower_bound(lsh+1,lsh+lt+1,e[i])-lsh;
llsh[i]=mpr(s[i],i);
tmpv[s[i]].pb(i);
idt[i]=++idcnt;
idf[i]=++idcnt;
}
sort(llsh+1,llsh+n+1);
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i];
addedge(idf[a[i]],idt[b[i]]);
addedge(idf[b[i]],idt[a[i]]);
}
rt[lt+1]=0;
for(int l=lt;l;l--){
rt[l]=rt[l+1];
for(int i:tmpv[l]){
int pos=lower_bound(llsh+1,llsh+n+1,mpr(s[i],i))-llsh;
int o=0;
ins(o,rt[l],1,n,pos,idf[i],0);
rt[l]=o;
}
}
for(int i=1;i<=n;i++){
int pos=lower_bound(llsh+1,llsh+n+1,mpr(s[i],i))-llsh;//no pos!
int up=lower_bound(llsh+1,llsh+n+1,mpr(e[i]+1,-114514))-llsh-1;
if(pos+1<=up)taddedge(rt[s[i]],1,n,pos+1,up,idt[i]);
if(1<=pos-1)taddedge(rt[e[i]],1,n,1,pos-1,idt[i]);
}
kosaraju();
int flag=1;
for(int i=1;i<=n;i++){
if(col[idt[i]]==col[idf[i]]){
flag=0;
}
}
if(flag)cout<<"YES\n";
else cout<<"NO\n";
clearup();
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 43ms
memory: 392692kb
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: -100
Memory Limit Exceeded
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:
YES