QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482728 | #8179. 2D Parentheses | cqbzly | WA | 120ms | 31920kb | C++14 | 2.4kb | 2024-07-17 20:58:14 | 2024-07-17 20:58:15 |
Judging History
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