QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422550#8179. 2D ParenthesesMathew_MiaoWA 360ms67636kbC++234.7kb2024-05-27 15:57:362024-05-27 15:57:37

Judging History

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

  • [2024-05-27 15:57:37]
  • 评测
  • 测评结果:WA
  • 用时:360ms
  • 内存:67636kb
  • [2024-05-27 15:57:36]
  • 提交

answer

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
const int N=2e5;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n;
struct node{
    int x,y,id,typ;
};
inline bool operator <(node a,node b){
    return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
}
inline bool cmp(node a,node b){
    return (a.y<b.y)||(a.y==b.y&&a.typ>b.typ)||(a.y==b.y&&a.typ==b.typ&&a.x<b.x);
}
node a[MAXN],b[MAXN];
node p[MAXN*2];
int px[MAXN*2],py[MAXN*2];
inline void discrete(){
    for(int i=1;i<=n;i++)
    {
        px[i]=a[i].x;
        py[i]=a[i].y;
        px[i+n]=b[i].x;
        py[i+n]=b[i].y;
    }
    sort(px+1,px+1+n*2);
    sort(py+1,py+1+n*2);
    int totx=unique(px+1,px+1+n*2)-px-1;
    int toty=unique(py+1,py+1+n*2)-py-1;
    for(int i=1;i<=n;i++)
    {
        a[i].x=lower_bound(px+1,px+1+totx,a[i].x)-px;
        a[i].y=lower_bound(py+1,py+1+toty,a[i].y)-py;
        b[i].x=lower_bound(px+1,px+1+totx,b[i].x)-px;
        b[i].y=lower_bound(py+1,py+1+toty,b[i].y)-py;
    }
}
int mat[MAXN*2];
multiset <node> s;
#define ull unsigned long long
namespace segtree{
    int L[MAXN*8],R[MAXN*8];
    ull hsh[MAXN*8],tag[MAXN*8];
    bool same[MAXN*8];
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    inline void push_up(int x){
        hsh[x]=hsh[ls(x)];
        same[x]=same[ls(x)]&&same[rs(x)]&&(hsh[ls(x)]==hsh[rs(x)]);
    }
    inline void push_down(int x){
        if(!tag[x]){
            return ;
        }
        hsh[ls(x)]^=tag[x];
        tag[ls(x)]^=tag[x];
        hsh[rs(x)]^=tag[x];
        tag[rs(x)]^=tag[x];
        tag[x]=0;
    }
    void build(int l,int r,int x){
        L[x]=l;
        R[x]=r;
        same[x]=true;
        if(l==r){
            return ;
        }
        int mid=(l+r)/2;
        build(l,mid,ls(x));
        build(mid+1,r,rs(x));
    }
    inline void build(){
        build(1,n*2,1);
    }
    void modify(int ql,int qr,ull val,int x){
        int l=L[x],r=R[x];
        if(ql<=l&&r<=qr){
            hsh[x]^=val;
            tag[x]^=val;
            return ;
        }
        if(r<ql||qr<l){
            return ;
        }
        push_down(x);
        modify(ql,qr,val,ls(x));
        modify(ql,qr,val,rs(x));
        push_up(x);
    }
    inline void modify(int ql,int qr,ull val){
        modify(ql,qr,val,1);
    }
    ull lst;
    bool fir;
    bool query(int ql,int qr,int x){
        int l=L[x],r=R[x];
        if(ql<=l&&r<=qr){
            if(!fir){
                lst=hsh[x];
                fir=true;
            }
            return same[x]&&(lst==hsh[x]);
        }
        if(r<ql||qr<l){
            return true;
        }
        push_down(x);
        return query(ql,qr,ls(x))&&query(ql,qr,rs(x));
    }
    inline bool query(int ql,int qr){
        fir=false;
        return query(ql,qr,1);
    }
}
struct Qry{
    int pos,l,r,typ;
    ull hsh;
}q[MAXN*2];
inline bool operator <(Qry x,Qry y){
    if(x.pos^y.pos){
        return x.pos<y.pos;
    }
    if(x.typ^y.typ){
        return x.typ<y.typ;
    }
    if(x.typ){
        return x.r-x.l>y.r-y.l;
    }
    else{
        return x.r-x.l<y.r-y.l;
    }
}
#include<random>
mt19937_64 rnd(372409);
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].typ=0;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&b[i].x,&b[i].y);
        b[i].typ=1;
        b[i].id=i;
    }
    discrete();
    for(int i=1;i<=n;i++)
    {
        p[i]=a[i];
        p[i+n]=b[i];
    }
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n*2;i++)
    {
        if(!p[i].typ){
            s.insert(p[i]);
        }
        else{
            multiset <node>::iterator it=s.lower_bound(node{p[i].x-1,p[i].y,p[i].id,p[i].typ});
            if(it==s.begin()){
                puts("No");
                return 0;
            }
            it--;
            mat[it->id]=p[i].id;
            s.erase(it);
        }
    }
    segtree::build();
    for(int i=1;i<=n;i++)
    {
        ull now=rnd();
        q[i]=Qry{a[i].x,a[i].y,b[mat[i]].y,1,now};
        q[i+n]=Qry{b[mat[i]].x,a[i].y,b[mat[i]].y,0,now};
    }
    sort(q+1,q+1+n*2);
    for(int i=1;i<=n*2;i++)
    {
        segtree::modify(q[i].l,q[i].r-1,q[i].hsh);
        if(!segtree::query(q[i].l,q[i].r-1)){
            puts("No");
            exit(0);
        }
    }
    puts("Yes");
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",mat[i]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 22344kb

input:

3
0 0
2 -2
1 1
2 2
3 1
2 3

output:

Yes
3
2
1

result:

ok answer is YES, 3 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 24268kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 3ms
memory: 15876kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 360ms
memory: 67636kb

input:

199996
94702923 895749121
-830347683 823853414
-638337012 -528381915
774504965 -903560893
465975432 931026841
47062323 901390864
539345338 830099354
278774201 896803047
-445303873 568413124
80473317 828648317
804283391 -307873779
543648687 893783688
814084625 -664894626
169476937 -999435847
-8232728...

output:

No

result:

wrong answer expected YES, found NO