QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#223900#6633. Exam RequirementsNerovixWA 485ms333856kbC++144.1kb2023-10-22 20:12:342023-10-22 20:12:36

Judging History

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

  • [2023-10-22 20:12:36]
  • 评测
  • 测评结果:WA
  • 用时:485ms
  • 内存:333856kb
  • [2023-10-22 20:12:34]
  • 提交

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*30;
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[s[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;
}

詳細信息

Test #1:

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

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
Wrong Answer
time: 485ms
memory: 333856kb

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

result:

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