QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#619695 | #8179. 2D Parentheses | Fiyuls | WA | 354ms | 24488kb | C++14 | 3.2kb | 2024-10-07 15:04:31 | 2024-10-07 15:04:31 |
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()){
if(n>=100){
cout<<"nodgd";return 0;
}
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+1,pa[i].ry-1)){
if(n>=100){
cout<<i<<" "<<j<<endl;
for(int k=1;k<=j;k++){
cout<<pa[k].x<<" "<<pa[k].ly<<" "<<pa[k].ry<<" "<<pa[k].op<<endl;
}
}
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: 1ms
memory: 10088kb
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: 7912kb
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: 12072kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: 0
Accepted
time: 343ms
memory: 22724kb
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 21701 88398 59327 146960 29196 103293 198434 198023 157367 48765 157321 148908 80650 112519 196489 172199 173973 5551 141927 136548 134111 182366 59175 165032 163355 57765 5843 31857 130090 185365 76890 97333 133685 142517 167272 4006 171963 1988 107334 183071 65560 70618 199137 151179 183975 10...
result:
ok answer is YES, 199996 tokens
Test #5:
score: 0
Accepted
time: 341ms
memory: 22908kb
input:
199989 -185038489 939943355 404432727 -854751373 554853823 193640691 301504969 -998071590 274900356 938454158 -432464517 285421885 405518801 -987371480 571222708 909692099 -759427030 -999520045 869336666 847296633 -622724138 -999895334 -54035108 -876650516 453457981 -842759465 892363710 -794270574 1...
output:
Yes 29051 42308 37337 84855 166499 109338 34862 199409 32310 182823 20620 177599 116234 29219 168881 98498 20908 64603 145113 95741 106479 41666 136146 57568 153800 159627 73275 187439 74915 2272 25123 152755 131852 155786 59824 193752 26923 55748 13026 132594 87769 26528 189799 148030 136086 143680...
result:
ok answer is YES, 199989 tokens
Test #6:
score: 0
Accepted
time: 351ms
memory: 21960kb
input:
199991 -900159443 -671207779 -114175529 -885513466 -57386301 392144414 623068349 -990207451 -466916252 -379159070 -390577839 868367620 -142964637 -583431492 -288979694 -899596387 -357113786 867092775 833205097 992058046 -885274285 951889875 -406261261 872434960 -99080436 889619788 -37516399 -2293017...
output:
Yes 3275 63270 93912 127141 22479 165152 198171 26948 80966 36189 160851 192441 14819 41768 118467 117142 19608 136232 104951 109409 47223 99091 151706 110331 54762 66016 16120 166582 89823 77684 49744 74404 47622 182252 83554 97967 190281 111679 20281 17322 79190 103090 116209 40445 137659 13013 24...
result:
ok answer is YES, 199991 tokens
Test #7:
score: 0
Accepted
time: 354ms
memory: 22700kb
input:
199987 -46649274 139363612 803504473 -487067218 -231304341 961630672 807256898 -256192650 -473216529 -412520640 387331113 961360032 -718008950 -1000000000 156200839 95571209 981893716 -29439313 -470730442 -783533869 799296462 104576693 -553698761 -906790634 807374303 -24023479 309903544 968199523 32...
output:
Yes 108253 39856 69761 52978 95487 52526 165960 5834 154779 176120 98055 116863 185474 199758 158834 7618 59391 94556 148087 135584 103212 46150 11774 57061 193721 73508 53857 107232 28635 11110 92043 112059 176064 91995 182180 157770 164760 94634 170392 57167 64585 147769 177684 141597 196364 5163 ...
result:
ok answer is YES, 199987 tokens
Test #8:
score: 0
Accepted
time: 346ms
memory: 22432kb
input:
199998 520404957 315206955 589123511 -430859516 376860728 -987316121 614664700 -301663049 978007244 -969619964 636107820 259251657 137671843 -958442271 549117430 -935982467 341044573 -957188402 920491566 768041266 584917074 -822386658 170473403 -165076605 528955497 239159653 608627148 -761435336 294...
output:
Yes 82347 108348 69489 26272 38797 5634 171949 36739 168135 91411 33031 55676 52141 104041 168253 25828 64027 133931 106943 41392 145594 100287 149043 92143 168786 81236 24112 157854 150937 77525 2953 98374 15882 5118 86665 187254 96225 44878 26976 116891 140926 67595 136505 12406 158887 133562 1802...
result:
ok answer is YES, 199998 tokens
Test #9:
score: -100
Wrong Answer
time: 248ms
memory: 24488kb
input:
199993 -751151977 -533994506 -927773836 -32372872 56850331 -243441225 327514682 -361038889 247003430 -838950588 -981662694 -566754857 -57613101 -102410474 857750386 -993733474 184906291 -664905204 -479853877 -891755682 851112690 -967524478 -597827988 -230528151 -782058930 -309016717 684473363 -93368...
output:
2 2 999999035 1 8 1 999998953 2 3072 1 No
result:
wrong output format YES or NO expected, but 2 found