QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618864#8179. 2D ParenthesesFiyulsWA 123ms23828kbC++143.1kb2024-10-07 11:09:202024-10-07 11:09:21

Judging History

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

  • [2024-10-07 11:09:21]
  • 评测
  • 测评结果:WA
  • 用时:123ms
  • 内存:23828kb
  • [2024-10-07 11:09:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define ULL unsigned long long
#define make(a,b) make_pair(a,b)
mt19937 RDom(time(0));
const int maxn=4e5+5;
struct node{
    int x,y,col,id;
    bool operator<(const node a)const{
        return (x==a.x)?y<a.y:x<a.x;
    }
    bool operator==(const node a)const{
        return x==a.x and y==a.y;
    }
    bool operator>(const node a)const{
        return (x==a.x)?y>a.y:x>a.x;
    }
}nd[maxn];
struct pand{
    int x,ly,ry,op;
    ULL id;
}pa[maxn];
int n,m,Cnt,lc,lisa[maxn],Comp[maxn];
set<node> sn;
ULL Tre[maxn<<2];
ULL query(int u,int stdl,int stdr,int l,int r){if(l>r)return 0;
    if(stdl==l and stdr==r){
        return Tre[u];
    }
    int mid=(stdl+stdr)>>1,lson=(u<<1),rson=lson+1;
    if(r<=mid)return query(lson,stdl,mid,l,r);else if(l>=mid+1)return query(rson,mid+1,stdr,l,r);
    else{
        return query(lson,stdl,mid,l,mid)+query(rson,mid+1,stdr,mid+1,r);
    }
}
void modify(int u,int stdl,int stdr,int x,ULL d){
    if(stdl==stdr){
        Tre[u]+=d;
        return;
    }
    int mid=(stdl+stdr)>>1,lson=(u<<1),rson=lson+1;
    if(x<=mid){
        modify(lson,stdl,mid,x,d);
    }else{
        modify(rson,mid+1,stdr,x,d);
    }
    Tre[u]=Tre[lson]+Tre[rson];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        Cnt++,scanf("%d%d",&nd[Cnt].x,&nd[Cnt].y),nd[Cnt].id=i,nd[Cnt].col=0,lisa[++lc]=nd[Cnt].y;
    }
    for(int i=1;i<=n;i++){
        Cnt++,scanf("%d%d",&nd[Cnt].x,&nd[Cnt].y),nd[Cnt].id=i,nd[Cnt].col=1,lisa[++lc]=nd[Cnt].y;
    }
    sort(nd+1,nd+1+Cnt,[](node a,node b){return (a.x==b.x)?((a.col==b.col)?a.y>b.y:a.col<b.col):a.x>b.x;});
    for(int i=1;i<=Cnt;i++){
        if(nd[i].col==1){
            sn.insert(nd[i]);
        }else{
            node found=nd[i];
            found.x++,found.y++;
            auto p=sn.lower_bound(found);
            if(p==sn.end()){
                printf("No");return 0;
            }
            ULL Hash=RDom();
            Comp[nd[i].id]=(*p).id,pa[++m]=pand{(*p).x,nd[i].y,(*p).y,+1,Hash},pa[++m]=pand{nd[i].x,nd[i].y,(*p).y,-1,Hash},sn.erase(p);
        }
    }
    if(n<=1000){
    sort(pa+1,pa+1+m,[](pand a,pand b){return (a.x==b.x)?a.op<b.op:a.x>b.x;}),sort(lisa+1,lisa+1+lc),lc=unique(lisa+1,lisa+1+lc)-(lisa+1);
    for(int i=1,j=1;i<=m;i++){
        pa[i].ly=lower_bound(lisa+1,lisa+1+lc,pa[i].ly)-lisa;
        pa[i].ry=lower_bound(lisa+1,lisa+1+lc,pa[i].ry)-lisa;
        while(pa[j].x!=pa[i].x){
            if(pa[j].op==1){
                modify(1,1,lc,pa[j].ly,+pa[j].id*pa[j].op);
                modify(1,1,lc,pa[j].ry,+pa[j].id*pa[j].op);
            }
            j++;
        }
        if(pa[i].op==1){
            if(query(1,1,lc,pa[i].ly+1,pa[i].ry-1)){
                printf("No");
                return 0;
            }
        }else{
            modify(1,1,lc,pa[i].ly,+pa[i].id*pa[i].op);
            modify(1,1,lc,pa[i].ry,+pa[i].id*pa[i].op);
        }
    }}
    printf("Yes\n");
    for(int i=1;i<=n;i++){
        printf("%d\n",Comp[i]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12220kb

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: 2ms
memory: 12156kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 123ms
memory: 23828kb

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
125911
24064
125993
60528
74780
103293
44858
198023
39416
30857
44526
53516
33755
111711
44237
109982
173973
190071
141927
72913
74270
98374
38650
29307
162909
78378
63476
31857
62483
22532
180060
22555
105965
79801
169542
156904
142534
4450
107334
79505
139898
22634
120670
22847
13162
7282
4073...

result:

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