QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485355#6632. Minimize Medianucup-team1525#WA 6ms44500kbC++203.1kb2024-07-20 16:49:442024-07-20 16:49:45

Judging History

This is the latest submission verdict.

  • [2024-07-20 16:49:45]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 44500kb
  • [2024-07-20 16:49:44]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5,T=1.1e6;
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+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 tr[T+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){
        tr[id]=++tot;
        if(l==r){
            adde(tr[id]<<1|1,tr[id]<<1);
            return;
        }
        int mid=l+r>>1;
        build(l,mid,lc);
        build(mid+1,r,rc);
        addex(tr[id],1,tr[lc],1);
        addex(tr[id],1,tr[rc],1);
    }
    void init(int n){
        for(int i=1;i<=tot;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){
            addex(u,1,tr[id],1);
            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);
    }
    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(){
        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);
    }
    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: 0
Wrong Answer
time: 6ms
memory: 44500kb

input:

3
3 5 0
2 5 2
3 2 4 6 13
3 5 3
2 5 3
3 2 4 6 13
3 5 6
2 5 2
3 2 4 6 13

output:

NO
NO
NO

result:

wrong output format Expected integer, but "NO" found