QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423972#8179. 2D ParenthesesCharlieVinnieRE 2ms3720kbC++202.8kb2024-05-28 20:17:032024-05-28 20:17:04

Judging History

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

  • [2024-05-28 20:17:04]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3720kb
  • [2024-05-28 20:17:03]
  • 提交

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;
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,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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Runtime Error

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:


result: