QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423979#8179. 2D ParenthesesCharlieVinnieWA 2ms3720kbC++203.7kb2024-05-28 20:24:432024-05-28 20:24:43

Judging History

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

  • [2024-05-28 20:24:43]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3720kb
  • [2024-05-28 20:24:43]
  • 提交

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 modify(int k,int l,int r,int ql,int qr,int x){
        if(ql<=l&&r<=qr) return tag[k]=MERGE(tag[k],x),O[k]=MERGE(O[k],x),void();
        int mid=(l+r)>>1;
        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(MERGE(O[k1],O[k2]),tag[k]);
    }
    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;
        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 MERGE(res,tag[k]);
    }
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: 0
Wrong Answer
time: 2ms
memory: 3720kb

input:

3
0 0
2 -2
1 1
2 2
3 1
2 3

output:

No

result:

wrong answer expected YES, found NO