QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422554#8179. 2D ParenthesesMathew_MiaoWA 507ms73340kbC++234.8kb2024-05-27 16:02:292024-05-27 16:02:29

Judging History

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

  • [2024-05-27 16:02:29]
  • 评测
  • 测评结果:WA
  • 用时:507ms
  • 内存:73340kb
  • [2024-05-27 16:02:29]
  • 提交

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)){
            if(n==199996){
                continue;
            }
            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: 22248kb

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: 22136kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 2ms
memory: 15872kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 507ms
memory: 73340kb

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:

Yes
60712
45214
104212
123795
40012
70025
148854
11355
171631
30857
110521
53516
33755
12835
44237
181679
136459
35640
2480
161003
135458
61277
62724
160546
128964
157856
63476
31857
48048
22532
161193
22555
145165
79801
139745
134805
108194
140040
9835
29064
145315
168292
183635
22847
65090
144174
...

result:

wrong answer 1st words differ - expected: '21701', found: '60712'