QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423287#8179. 2D ParenthesesVanilla_QwQWA 171ms18604kbC++142.7kb2024-05-27 22:05:262024-05-27 22:05:35

Judging History

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

  • [2024-05-27 22:05:35]
  • 评测
  • 测评结果:WA
  • 用时:171ms
  • 内存:18604kb
  • [2024-05-27 22:05:26]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#define LL long long
#define il inline
#define Pii pair<int, int>
#define fir first
#define sec second
#define SIZ(x) int(x.size())
#define ALL(x) x.begin(), x.end()
using namespace std;
const int MaxN = 2e5 + 3;
int N;
struct node{
    int x, y, id;
    bool operator < (const node &b) const {
        if(y == b.y) return x < b.x;
        return y < b.y;
    }
    bool operator > (const node &b) const {
    	return b < *this;
	}
} a[MaxN], b[MaxN];
set<Pii> st;
struct seg{
    int y, l, r, id, typ, ano_y;
} o[MaxN*2];
int c[MaxN];
il bool check(){
	multiset<int> st;
    sort(a+1, a+N+1, [&](const node &x, const node &y){
        return x.id < y.id;
    });
    sort(b+1, b+N+1, [&](const node &x, const node &y){
        return x.id < y.id;
    });
    int m = 0;
    for(int i = 1; i <= N; i++){
        auto &d = b[c[a[i].id]];
        o[++m] = {a[i].y, a[i].x, d.x, i, 1, 0};
        o[++m] = {d.y, a[i].x, d.x, i, -1, a[i].y};
    }
    sort(o+1, o+m+1, [&](const seg &a, const seg &b){
        if(a.y != b.y) return a.y < b.y;
        if(a.typ != b.typ) return a.typ > b.typ;
        if(a.typ == -1 && b.typ == -1) return a.ano_y > b.ano_y;
    });
//    for(int i = 1; i <= m; i++){
//    	cerr<<o[i].y<<' '<<o[i].l<<' '<<o[i].r<<' '<<o[i].id<<' '<<o[i].typ<<' '<<o[i].ano_y<<endl;
//	}
    for(int i = 1; i <= m; i++){
        auto &sg = o[i];
        int l = sg.l, r = sg.r;
        if(sg.typ == 1){
        	auto it = st.upper_bound(l);
            if(it != st.end() && *it < r) return false;
            st.insert(l), st.insert(r);
        }
        else {
        	auto it = st.upper_bound(l);
            if(it != st.end() && *it < r) return false;
            st.erase(st.find(l)), st.erase(st.find(r));
        }
   }
   return true;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>N;
    for(int i = 1, x, y; i <= N; i++) cin>>x>>y, a[i] = {x, y, i};
    for(int i = 1, x, y; i <= N; i++) cin>>x>>y, b[i] = {x, y, i};
    sort(a+1, a+N+1, less<>());
    sort(b+1, b+N+1, greater<>());
    for(int i = N, j = 0; i >= 1; i--) {
        while(j+1 <= N && b[j+1].y > a[i].y) j++, st.insert({b[j].x, b[j].id});
//        cerr<<i<<": "<<SIZ(st)<<endl;
        auto it = st.lower_bound({a[i].x, -1});
        if(it == st.end()){
            cout<<"No"<<'\n';
            return 0;
        }
        c[a[i].id] = it->sec;
        st.erase(it);
    }
//    cerr<<"?"<<endl;
//    for(int i = 1; i <= N; i++) cerr<<c[i]<<'\n';
    if(check()){
        cout<<"Yes"<<'\n';
        for(int i = 1; i <= N; i++) cout<<c[i]<<'\n';
    }
    else cout<<"No"<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 7944kb

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 171ms
memory: 18604kb

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