QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#482728#8179. 2D ParenthesescqbzlyWA 120ms31920kbC++142.4kb2024-07-17 20:58:142024-07-17 20:58:15

Judging History

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

  • [2024-07-17 20:58:15]
  • 评测
  • 测评结果:WA
  • 用时:120ms
  • 内存:31920kb
  • [2024-07-17 20:58:14]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define rz resize
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e6+5;
int n,sz[2],lsh[N],cnt,match[N],bit[N];
struct node{
    int x,y,id;
    bool operator <(const node &a)const{
        return x<a.x||x==a.x&&y<a.y;
    }
}a[2][N];
set<pair<pair<int,int>,int>>s;
pair<pair<int,int>,int>b[2][N];
void add(int l1,int r1,int l2,int r2){
    //cout<<"add:"<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
    b[0][++sz[0]]={{l1+1,l2},1},b[0][++sz[0]]={{r1,l2},-1};
    b[0][++sz[0]]={{l1+1,r2},1},b[0][++sz[0]]={{r1,r2},-1};
    b[1][++sz[1]]={{l1,l2},r2-1},b[1][++sz[1]]={{r1,l2},r2-1};
    lsh[++cnt]=l2,lsh[++cnt]=r2-1,lsh[++cnt]=r2;
}
int get(int x){
    return lower_bound(lsh+1,lsh+1+cnt,x)-lsh;
}
void ad(int x,int y){
    for(;x<=cnt;x+=x&-x)bit[x]+=y;
}
int ask(int x){
    int y=0;
    for(;x;x-=x&-x)y+=bit[x];
    return y;
}
int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<2;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j].x>>a[i][j].y,a[i][j].id=j;
        }
    }
    for(int i=0;i<2;i++)sort(a[i]+1,a[i]+1+n);
    int j=n;
    for(int i=n;i>=1;i--){
        while(j>=1&&a[1][j].x>a[0][i].x){
            s.insert({{a[1][j].y,a[1][j].x},a[1][j].id});
            j--;
        }
        auto it=s.lower_bound({{a[0][i].y+1,0},0});
        if(it!=s.end()){
            match[a[0][i].id]=it->se;
            add(a[0][i].x,it->fi.se,a[0][i].y,it->fi.fi);
            s.erase(it);
        }
        else{
            //cout<<"find:"<<a[0][i].x<<" "<<a[0][i].y<<"\n";
            cout<<"No";
            return 0;
        }
    }
    sort(lsh+1,lsh+1+cnt),cnt=unique(lsh+1,lsh+1+cnt)-lsh-1;
    for(int i=0;i<2;i++)sort(b[i]+1,b[i]+1+sz[i]);
    j=1;
    for(int i=1;i<=sz[1];i++){
        while(j<=sz[0]&&b[0][j].fi.fi<=b[1][i].fi.fi){
            //cout<<"add:"<<b[0][j].fi.se<<" "<<b[0][j].se<<"\n";
            ad(get(b[0][j].fi.se),b[0][j].se);
            j++;
        }
        if(ask(get(b[1][i].se))-ask(get(b[1][i].fi.se))>0){
            //cout<<"find:"<<b[1][i].se<<" "<<b[1][i].fi.se<<" "<<b[1][i].fi.fi<<" "<<b[0][j].fi.fi<<"\n";
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes"<<"\n";
    for(int i=1;i<=n;i++)cout<<match[i]<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 0ms
memory: 7840kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 120ms
memory: 31920kb

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