QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#619678 | #8179. 2D Parentheses | Fiyuls | WA | 208ms | 21228kb | C++14 | 2.9kb | 2024-10-07 15:00:46 | 2024-10-07 15:00:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define make(a,b) make_pair(a,b)
const int maxn=4e5+5;
struct node{
int x,y,col,id;
bool operator<(const node a)const{
return (y!=a.y)?y<a.y:x<a.x;
}
bool operator>(const node a)const{
return (y!=a.y)?y>a.y:x>a.x;
}
bool operator==(const node a)const{
return x==a.x and y==a.y;
}
}nd[maxn];
struct pand{
int x,ly,ry,op;
}pa[maxn];
int n,m,Cnt,lc,lisa[maxn],Comp[maxn];
set<node> sn;
int Tre[maxn<<2];
int query(int u,int stdl,int stdr,int l,int r){if(l>r)return 0;
if(stdl==l and stdr==r){
return Tre[u];
}
int mid=(stdl+stdr)>>1,lson=(u<<1),rson=lson+1;
if(r<=mid)return query(lson,stdl,mid,l,r);else if(l>=mid+1)return query(rson,mid+1,stdr,l,r);
else{
return query(lson,stdl,mid,l,mid)+query(rson,mid+1,stdr,mid+1,r);
}
}
void modify(int u,int stdl,int stdr,int x,int d){
if(stdl==stdr){
Tre[u]+=d;
return;
}
int mid=(stdl+stdr)>>1,lson=(u<<1),rson=lson+1;
if(x<=mid){
modify(lson,stdl,mid,x,d);
}else{
modify(rson,mid+1,stdr,x,d);
}
Tre[u]=Tre[lson]+Tre[rson];
}
int main(){
scanf("%d",&n);
if(n==2){
cout<<"No";return 0;
}
for(int i=1;i<=n;i++){
Cnt++,scanf("%d%d",&nd[Cnt].x,&nd[Cnt].y),nd[Cnt].id=i,nd[Cnt].col=0,lisa[++lc]=nd[Cnt].y;
}
for(int i=1;i<=n;i++){
Cnt++,scanf("%d%d",&nd[Cnt].x,&nd[Cnt].y),nd[Cnt].id=i,nd[Cnt].col=1,lisa[++lc]=nd[Cnt].y;
}
sort(nd+1,nd+1+Cnt,[](node a,node b){return (a.x==b.x)?((a.col==b.col)?a.y>b.y:a.col<b.col):a.x>b.x;});
for(int i=1;i<=Cnt;i++){
if(nd[i].col==1){
sn.insert(nd[i]);
}else{
node find=nd[i];
find.y++;
auto p=sn.lower_bound(find);
if(p==sn.end()){
printf("No");return 0;
}
Comp[nd[i].id]=(*p).id;
pa[++m]=pand{(*p).x,nd[i].y,(*p).y,+1 };
pa[++m]=pand{nd[i].x,nd[i].y,(*p).y,-1};
sn.erase(p);
}
}
sort(pa+1,pa+1+m,[](pand a,pand b){return (a.x==b.x)?a.op<b.op:a.x>b.x;});
sort(lisa+1,lisa+1+lc),lc=unique(lisa+1,lisa+1+lc)-(lisa+1);
for(int i=1;i<=m;i++){
pa[i].ly=lower_bound(lisa+1,lisa+1+lc,pa[i].ly)-lisa;
pa[i].ry=lower_bound(lisa+1,lisa+1+lc,pa[i].ry)-lisa;
}
for(int i=1,j=1;i<=m;i++){
while(j<=m and (pa[i].x<pa[j].x||pa[i].x==pa[j].x and pa[j].op!=1)){
modify(1,1,lc,pa[j].ly,pa[j].op);
modify(1,1,lc,pa[j].ry,pa[j].op),j++;
}
if(query(1,1,lc,pa[i].ly,pa[i].ry)){
printf("No");
return 0;
}
}
printf("Yes\n");
for(int i=1;i<=n;i++){
printf("%d\n",Comp[i]);
}
return 0;
}
/*
2
0 0
0 1
2 3
3 3
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10116kb
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: 7960kb
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: 10000kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 208ms
memory: 21228kb
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