QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423984#8179. 2D ParenthesesCharlieVinnieWA 443ms58016kbC++203.8kb2024-05-28 20:28:372024-05-28 20:28:37

Judging History

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

  • [2024-05-28 20:28:37]
  • 评测
  • 测评结果:WA
  • 用时:443ms
  • 内存:58016kb
  • [2024-05-28 20:28:37]
  • 提交

answer

// #define _GLIBCXX_DEBUG
#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define fi first
#define se second
using namespace std; typedef long long ll;
constexpr int N=4e5+5; using pii = pair<int,int>; using tiii = tuple<int,int,int>;
int MERGE(int x,int y) { if(x==-1||y==-1) return -1;; if(x==0||y==0) return x^y;; if(x==y) return x; else return -1; }
// class STree{
//     int n,a[N];
// public:
//     void init(int _n) { n=_n; }
//     void modify(int l,int r,int x) { For(i,l,r) a[i]=x; }
//     int query(int l,int r) { int res=0; For(i,l,r) res=MERGE(res,a[i]);; return res; }
// }T;
class STree{
    int n,O[N<<2],tag[N<<2];
    #define k1 (k<<1)
    #define k2 (k<<1|1)
    void setg(int k,int x) { tag[k]=O[k]=x; }
    void pushdown(int k) { if(tag[k]) setg(k1,tag[k]),setg(k2,tag[k]),tag[k]=0; }
    void modify(int k,int l,int r,int ql,int qr,int x){
        if(ql<=l&&r<=qr) return setg(k,x),void();
        int mid=(l+r)>>1; pushdown(k);
        if(ql<=mid) modify(k1,l,mid,ql,qr,x);
        if(mid+1<=qr) modify(k2,mid+1,r,ql,qr,x);
        O[k]=MERGE(O[k1],O[k2]);
    }
    int query(int k,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return O[k];
        int mid=(l+r)>>1,res=0; pushdown(k);
        if(ql<=mid) res=MERGE(res,query(k1,l,mid,ql,qr));
        if(mid+1<=qr) res=MERGE(res,query(k2,mid+1,r,ql,qr));
        return res;
    }
public:
    void init(int _n) { n=_n; }
    void modify(int l,int r,int x) { modify(1,1,n,l,r,x); }
    int query(int l,int r) { return query(1,1,n,l,r); }
}T;
void Discrete(int* a,int n,int* tmp,int& tcnt){
    tcnt=0; For(i,1,n) tmp[++tcnt]=a[i];
    sort(tmp+1,tmp+1+tcnt); tcnt=unique(tmp+1,tmp+1+tcnt)-(tmp+1);
    For(i,1,n) a[i]=lower_bound(tmp+1,tmp+1+tcnt,a[i])-tmp;
}
int n,X[N],Y[N],tmpx[N],tcntx,tmpy[N],tcnty,ans[N],tot,fa[N]; vector<pii> lis[N][2]; struct Op { int l,r,id; }; vector<Op> add[N],del[N];
[[noreturn]] void NO() { cout<<"No\n"; exit(0); }
void Add(int u,int v){
    debug(u,v);
    assert(u<=n&&v>n&&X[u]<X[v]&&Y[u]<Y[v]);
    ans[u]=v-n; tot++;
    add[X[u]  ].emplace_back(Op{Y[u],Y[v]-1,tot});
    del[X[v]-1].emplace_back(Op{Y[u],Y[v]-1,tot});
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    cin>>n; For(i,1,n*2) cin>>X[i]>>Y[i];
    Discrete(X,n*2,tmpx,tcntx), Discrete(Y,n*2,tmpy,tcnty);
    For(i,1,n*2) lis[X[i]][i>n].emplace_back(Y[i],i);
    multiset<tiii> S;
    For(i,1,tcntx){
        for(auto [y,id]:lis[i][1]){
            auto it=S.lower_bound(tiii(y-1,0,0));
            if(it==S.begin()) NO();
            int o=get<2>(*--it);
            Add(o,id);
            S.erase(it);
        }
        for(auto [y,id]:lis[i][0]) S.emplace(y,-i,id);
    }
    T.init(tcnty-1);
    For(i,1,tcntx){
        sort(add[i].begin(),add[i].end(),[](Op A,Op B){return pii(A.r-A.l,A.id)>pii(B.r-B.l,B.id);});
        sort(del[i].begin(),del[i].end(),[](Op A,Op B){return pii(A.r-A.l,A.id)<pii(B.r-B.l,B.id);});
        for(auto [l,r,id]:add[i]){
            debug(i,l,r,id);
            int c=T.query(l,r); if(c==-1) NO();
            fa[id]=c; T.modify(l,r,id);
        }
        for(auto [l,r,id]:del[i]){
            debug(i,l,r,id);
            int c=T.query(l,r);if(c!=id) NO();
            T.modify(l,r,fa[id]);
        }
    }
    cout<<"Yes\n"; For(i,1,n) cout<<ans[i]<<'\n';
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: May 27 Mon, 20 : 55 : 45

詳細信息

Test #1:

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

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

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 4ms
memory: 13804kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 443ms
memory: 58016kb

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