QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618886 | #8179. 2D Parentheses | Fiyuls | WA | 122ms | 24484kb | C++14 | 3.0kb | 2024-10-07 11:22:28 | 2024-10-07 11:22:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define ULL unsigned long long
#define make(a,b) make_pair(a,b)
mt19937 RDom(time(0));
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;
ULL id;
}pa[maxn];
int n,m,Cnt,lc,lisa[maxn],Comp[maxn];
set<node> sn;
ULL Tre[maxn<<2];
ULL 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,ULL 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);
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{
auto p=sn.upper_bound(nd[i]);
if(p==sn.end()){
printf("No");return 0;
}
ULL Hash=RDom();
Comp[nd[i].id]=(*p).id,pa[++m]=pand{(*p).x,nd[i].y,(*p).y,+1,Hash},pa[++m]=pand{nd[i].x,nd[i].y,(*p).y,-1,Hash},sn.erase(p);
}
}
if(n<=1000){
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,j=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;
while(pa[j].x!=pa[i].x){
if(pa[j].op==1){
modify(1,1,lc,pa[j].ly,+pa[j].id*pa[j].op);
modify(1,1,lc,pa[j].ry,+pa[j].id*pa[j].op);
}
j++;
}
if(pa[i].op==1){
if(query(1,1,lc,pa[i].ly+1,pa[i].ry-1)){
printf("No");
return 0;
}
}else{
modify(1,1,lc,pa[i].ly,+pa[i].id*pa[i].op);
modify(1,1,lc,pa[i].ry,+pa[i].id*pa[i].op);
}
}}
printf("Yes\n");
for(int i=1;i<=n;i++){
printf("%d\n",Comp[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10120kb
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: 10052kb
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: 12104kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 122ms
memory: 24484kb
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:
Yes 164447 162486 85506 52754 29196 103293 14731 198023 157367 48765 173490 49262 137133 196363 186804 82724 78032 34701 44848 136548 75444 59067 176362 165032 96898 44935 5843 122285 62483 137571 76890 97333 30640 85853 77371 28165 115046 1988 107334 185925 183211 91317 35771 179081 10550 101854 39...
result:
wrong answer 1st words differ - expected: '21701', found: '164447'