QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#423237 | #8179. 2D Parentheses | Xun_xiaoyao | WA | 261ms | 15400kb | C++14 | 4.2kb | 2024-05-27 21:47:05 | 2024-05-27 21:47:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;bool f=false;char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return f?-x:x;
}
typedef pair<int,int> pr;
int n,bk1[200010],bk2[200010];
pr p1[200010],p2[200010];
int X[400010],Y[400010],totx,toty;
int fl1,fl2;
int pp[200010],p_[200010],fa[200010];
#define ls (pos<<1)
#define rs (pos<<1|1)
#define mid (l+r>>1)
int s[2000010],mx[200010],mn[200010];
void pushdown(int pos){if(s[pos]) mx[ls]=mn[ls]=s[ls]=mx[rs]=mn[rs]=s[rs]=s[pos],s[pos]=0;}
void update(int pos){mx[pos]=max(mx[ls],mx[rs]),mn[pos]=min(mn[ls],mn[rs]);}
int get_nd(int x,int pos=1,int l=1,int r=toty)
{
if(l==r) return s[pos];
if(x<=mid) return pushdown(pos),get_nd(x,ls,l,mid);
else return pushdown(pos),get_nd(x,rs,mid+1,r);
}
void range_change(int L,int R,int x,int pos=1,int l=1,int r=toty)
{
if(L<=l&&r<=R) return s[pos]=x,void();
if(r<L||R<l) return;
return pushdown(pos),range_change(L,R,x,ls,l,mid),range_change(L,R,x,rs,mid+1,r),update(pos);
}
int range_max(int L,int R,int pos=1,int l=1,int r=toty)
{
if(L<=l&&r<=R) return mx[pos];
if(r<L||R<l) return -20070610;
else return pushdown(pos),max(range_max(L,R,ls,l,mid),range_max(L,R,rs,mid+1,r));
}
int range_min(int L,int R,int pos=1,int l=1,int r=toty)
{
if(L<=l&&r<=R) return mn[pos];
if(r<L||R<l) return 20070610;
else return pushdown(pos),min(range_min(L,R,ls,l,mid),range_min(L,R,rs,mid+1,r));
}
void show(int pos=1,int l=1,int r=toty)
{
if(l==r) printf("%d ",s[pos]);
else pushdown(pos),show(ls,l,mid),show(rs,mid+1,r);
}
#undef ls
#undef rs
#undef mid
#define x first
#define y second
struct Node{pr loc;int id;};
bool operator<(Node A,Node B)
{
if(A.loc.y!=B.loc.y) return A.loc.y<B.loc.y;
if(A.loc.x!=B.loc.x) return A.loc.x<B.loc.x;
return false;
}
set<Node> S;set<Node>::iterator it;
int main()
{
n=Qread();
for(int i=1;i<=n;i++) p1[i].x=Qread(),p1[i].y=Qread();
for(int i=1;i<=n;i++) p2[i].x=Qread(),p2[i].y=Qread();
for(int i=1;i<=n;i++) X[++totx]=p1[i].x,Y[++toty]=p1[i].y;
for(int i=1;i<=n;i++) X[++totx]=p2[i].x,Y[++toty]=p2[i].y;
sort(X+1,X+totx+1);totx=unique(X+1,X+totx+1)-X-1;
sort(Y+1,Y+toty+1);toty=unique(Y+1,Y+toty+1)-Y-1;
for(int i=1;i<=n;i++) p1[i].x=lower_bound(X+1,X+totx+1,p1[i].x)-X,p1[i].y=lower_bound(Y+1,Y+toty+1,p1[i].y)-Y;
for(int i=1;i<=n;i++) p2[i].x=lower_bound(X+1,X+totx+1,p2[i].x)-X,p2[i].y=lower_bound(Y+1,Y+toty+1,p2[i].y)-Y;
// for(int i=1;i<=n;i++) printf("(%d %d)",p1[i].x,p1[i].y);printf("\n");
// for(int i=1;i<=n;i++) printf("(%d %d)",p2[i].x,p2[i].y);printf("\n");
for(int i=1;i<=n;i++) bk2[i]=i;
sort(bk2+1,bk2+n+1,[&](int a,int b){return p1[a]<p1[b];});
for(int i=1;i<=n;i++) bk1[bk2[i]]=i;
sort(bk2+1,bk2+n+1,[&](int a,int b){return p2[a]<p2[b];});
sort(p1+1,p1+n+1),sort(p2+1,p2+n+1);
// for(int i=1;i<=n;i++) printf("(%d %d)",p1[i].x,p1[i].y);printf("\n");
// for(int i=1;i<=n;i++) printf("(%d %d)",p2[i].x,p2[i].y);printf("\n");
fl1=fl2=1;
while(fl1<=n&&fl2<=n)
{
if(p2[fl2].x<=p1[fl1].x)
{
it=S.lower_bound(Node{make_pair(0,p2[fl2].y),fl2});
if(it==S.begin()) return printf("No\n"),0;
it--;
pp[it->id]=fl2,p_[fl2]=it->id;S.erase(it);
fl2++;
}
else S.insert(Node{p1[fl1],fl1}),fl1++;
}
if(fl1<=n) return printf("No\n"),0;
while(fl2<=n)
{
it=S.lower_bound(Node{make_pair(0,p2[fl2].y),fl2});
if(it==S.begin()) return printf("No\n"),0;
it--;
pp[it->id]=fl2;S.erase(it);
fl2++;
}
// for(int i=1;i<=n;i++) printf("[%d %d]*[%d %d]\n",p1[i].x,p2[pp[i]].x,p1[i].y,p2[pp[i]].y);
fl1=fl2=1;
int tl,tr;
while(fl1<=n&&fl2<=n)
{
if(p2[fl2].x<=p1[fl1].x)
{
range_change(p1[p_[fl2]].y,p2[fl2].y-1,fa[p_[fl2]]);
fl2++;
}
else
{
tl=get_nd(p1[fl1].y),tr=get_nd(p2[pp[fl1]].y-1);
if(tl!=tr||range_max(p1[fl1].y,p2[pp[fl1]].y-1)!=range_min(p1[fl1].y,p2[pp[fl1]].y-1)) return printf("No\n"),0;
if(tl&&p2[pp[fl1]].x>p2[pp[tl]].x) return printf("No\n"),0;
range_change(p1[fl1].y,p2[pp[fl1]].y-1,fl1);
fa[fl1]=tl;
fl1++;
}
// printf("%d %d:\n",fl1,fl2);
// show();printf("\n");
}
printf("Yes\n");
for(int i=1;i<=n;i++) printf("%d\n",bk2[pp[bk1[i]]]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12068kb
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: 11992kb
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: 9904kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 261ms
memory: 15400kb
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