QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485327#6632. Minimize Medianucup-team1525#RE 0ms0kbC++202.0kb2024-07-20 16:28:202024-07-20 16:28:20

Judging History

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

  • [2024-07-20 16:28:20]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-20 16:28:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5,T=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);
    }
    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));
    }
    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(); e[i].shrink_to_fit();
        }
        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 work(){
        
    }
}S;
void solve(){
    scanf("%d %d",&n,&m);
    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;
    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;
        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
Runtime Error

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:


result: