QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#422630#8179. 2D Parenthesesmsk_samaWA 56ms12884kbC++143.0kb2024-05-27 17:42:182024-05-27 17:42:19

Judging History

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

  • [2024-05-27 17:42:19]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:12884kb
  • [2024-05-27 17:42:18]
  • 提交

answer

#include <bits/stdc++.h>
#define MISAKA main
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
const int N=2e5+10,inf=1e9,mod=998244353;
struct point{int x,y,id;}p1[N],p2[N];
struct line{int h,l,r,tp;ull v;}a[N];
struct Node{int ls,rs,mx;}t[N<<6];
int n,K=0,cnt=0,_cnt=0,root=0,_root=0,ans[N];
int mmax(int a,int b){return p1[a].x>p1[b].x?a:b;}
void update(int &now,ll L,ll R,int x,int id){
    // cerr<<L<<' '<<R<<' '<<x<<' '<<id<<endl;
    if(!now) now=++cnt;ll mid=L+R>>1;
    if(L==R){t[now].mx=id;return;}
    if(x<=mid) update(t[now].ls,L,mid,x,id);
    else update(t[now].rs,mid+1,R,x,id);
    t[now].mx=mmax(t[t[now].ls].mx,t[t[now].rs].mx);
}
int query(int now,ll L,ll R,int l,int r){
    if(L>r||R<l||!now) return 0;ll mid=L+R>>1;
    if(l<=L&&R<=r) return t[now].mx;
    return mmax(query(t[now].ls,L,mid,l,r),query(t[now].rs,mid+1,R,l,r));
}
bool cmp(point a,point b){return a.y<b.y;}
bool _cmp(line a,line b){return a.h!=b.h?a.h<b.h:a.tp<b.tp;}
ull rd(){return (ull)(-rand())^(ull)rand()*51342394ull^346212733455943ull;}
struct node{int ls,rs;ull sum;}tn[N<<6];
void upd(int &now,ll L,ll R,int x,ull k){
    if(!now) now=++_cnt;ll mid=L+R>>1;
    if(L==R){tn[now].sum+=k;return;}
    if(x<=mid) upd(tn[now].ls,L,mid,x,k);
    else upd(tn[now].rs,mid+1,R,x,k);
    tn[now].sum=tn[tn[now].ls].sum+tn[tn[now].rs].sum;
}
ull qry(int now,ll L,ll R,int l,int r){
    if(L>r||R<l||!now||l>r) return 0;
    if(l<=L&&R<=r) return tn[now].sum;
    ll mid=L+R>>1;
    return qry(tn[now].ls,L,mid,l,r)+qry(tn[now].rs,mid+1,R,l,r);
}
signed MISAKA(){
    srand(time(0));
    n=read();p1[0].x=-2ll*inf;t[0].mx=0;
    for(int i=1;i<=n;i++) p1[i].x=read(),p1[i].y=read(),p1[i].id=i;
    for(int i=1;i<=n;i++) p2[i].x=read(),p2[i].y=read(),p2[i].id=i;
    sort(p1+1,p1+n+1,cmp);sort(p2+1,p2+n+1,cmp);
    for(int i=1,p=0;i<=n;i++){
        while(p<n&&p1[p+1].y<p2[i].y){
            p++;
            // cout<<p1[p].x+inf<<endl;
            update(root,0,2ll*inf,p1[p].x+inf,p);
        }
        // cerr<<i<<' '<<p<<' '<<t[root].mx<<endl;
        int id=query(root,0,2ll*inf,0,p2[i].x-1+inf);
        if(!id){printf("No");return 0;}
        update(root,0,2ll*inf,p1[id].x+inf,0);
        ull val=rd();ans[p1[id].id]=p2[i].id;
        a[++K]=line{p1[id].y,p1[id].x,p2[i].x,1,val};
        a[++K]=line{p2[i].y,p1[id].x,p2[i].x,-1,val};
    }
    sort(a+1,a+K+1,_cmp);
    for(int i=1;i<=K;i++){
        if(a[i].tp==-1){
            upd(_root,0,2ll*inf,a[i].l+inf,-a[i].v);
            upd(_root,0,2ll*inf,a[i].r+inf,a[i].v);
        }else{
            if(qry(_root,0,2*inf,a[i].l+inf,a[i].r-1+inf)){printf("No");return 0;}
            upd(_root,0,2ll*inf,a[i].l+inf,a[i].v);
            upd(_root,0,2ll*inf,a[i].r+inf,-a[i].v);
        }
    }
    printf("Yes\n");
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

详细

Test #1:

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

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

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 1ms
memory: 9936kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 56ms
memory: 12884kb

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