QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618864 | #8179. 2D Parentheses | Fiyuls | WA | 123ms | 23828kb | C++14 | 3.1kb | 2024-10-07 11:09:20 | 2024-10-07 11:09:21 |
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 (x==a.x)?y<a.y:x<a.x;
}
bool operator==(const node a)const{
return x==a.x and y==a.y;
}
bool operator>(const node a)const{
return (x==a.x)?y>a.y:x>a.x;
}
}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{
node found=nd[i];
found.x++,found.y++;
auto p=sn.lower_bound(found);
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: 2ms
memory: 12220kb
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: 2ms
memory: 12156kb
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: 10036kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 123ms
memory: 23828kb
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 125911 24064 125993 60528 74780 103293 44858 198023 39416 30857 44526 53516 33755 111711 44237 109982 173973 190071 141927 72913 74270 98374 38650 29307 162909 78378 63476 31857 62483 22532 180060 22555 105965 79801 169542 156904 142534 4450 107334 79505 139898 22634 120670 22847 13162 7282 4073...
result:
wrong answer 1st words differ - expected: '21701', found: '125911'