QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422957#8179. 2D Parenthesesmsk_samaWA 338ms59860kbC++143.1kb2024-05-27 20:29:512024-05-27 20:29:52

Judging History

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

  • [2024-05-27 20:29:52]
  • 评测
  • 测评结果:WA
  • 用时:338ms
  • 内存:59860kb
  • [2024-05-27 20:29:51]
  • 提交

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=1e6+10,inf=1e9+1,mod=998244353;
struct point{
    int x,y,id;
    friend bool operator<(point a,point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
}p1[N],p2[N];multiset<point> s;
struct line{int h,l,r,tp;ull v;}a[N];
int n,K=0,cnt=0,root=0,ans[N],b[N],len=0;
map<int,int> mp;
ull rd(){return (ull)(-rand())^(ull)rand()*rand()^3462127334545943ull;}
struct node{int l,r,tag;ull val,lazy;}t[N<<2];
void build(int now,int l,int r){
    t[now].l=l,t[now].r=r;t[now].tag=1;
    if(l==r) return;int mid=l+r>>1;
    build(2*now,l,mid);build(2*now+1,mid+1,r);
}
void pushup(int now){
    t[now].tag=t[2*now].tag&&t[2*now+1].tag&&t[2*now].val==t[2*now+1].val;
    t[now].val=t[2*now].val;
}
void cal(int now,ull x){t[now].val^=x,t[now].lazy^=x;}
void pushdown(int now){
    if(!t[now].lazy) return;
    cal(2*now,t[now].lazy);
    cal(2*now+1,t[now].lazy);
    t[now].lazy=0;
}
void upd(int now,int l,int r,ull x){
    if(t[now].l>r||t[now].r<l) return;
    if(l<=t[now].l&&t[now].r<=r) return cal(now,x);
    pushdown(now);
    upd(2*now,l,r,x);upd(2*now+1,l,r,x);
    pushup(now);
}
node qry(int now,int l,int r){
    if(t[now].l>r||t[now].r<l) return node{0,0,1,0,0};
    if(l<=t[now].l&&t[now].r<=r) return t[now];
    pushdown(now);ll mid=t[now].l+t[now].r>>1;
    if(r<=mid) return qry(2*now,l,r);
    if(l>mid) return qry(2*now+1,l,r);
    node a=qry(2*now,l,r),b=qry(2*now+1,l,r);
    node res;res.tag=a.tag&&b.tag&&a.val==b.val;res.val=a.val;
    return res;
}
bool cmp(point a,point b){return a.y!=b.y?a.y<b.y:a.x<b.x;}
bool _cmp(line a,line b){
    if(a.h!=b.h) return a.h<b.h;
    if(a.tp!=b.tp) return a.tp<b.tp;
    if(a.tp==1) return a.r-a.l>b.r-b.l;
    return a.r-a.l<b.r-b.l;
}
signed MISAKA(){
    srand(time(0));n=read();t[0].tag=1;
    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) s.insert(p1[++p]);
        auto it=s.lower_bound(p2[i]);
        if(it==s.begin()){printf("No");return 0;}
        it--;ans[(*it).id]=p2[i].id;s.erase(it);
        ull val=rd();int id=(*it).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};
        b[++len]=p1[id].x;b[++len]=p2[i].x;
    }
    sort(b+1,b+len+1);len=unique(b+1,b+len+1)-(b+1);
    for(int i=1;i<=len;i++) mp[b[i]]=i;
    for(int i=1;i<=K;i++) a[i].l=mp[a[i].l],a[i].r=mp[a[i].r];
    sort(a+1,a+K+1,_cmp);
    build(1,1,len);
    for(int i=1;i<=K;i++){
        node t=qry(1,a[i].l,a[i].r-1);
        if(!t.tag){printf("No");return 0;}
        upd(1,a[i].l,a[i].r-1,a[i].v);
    }
    printf("Yes\n");
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 338ms
memory: 59860kb

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