QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422544 | #8179. 2D Parentheses | Mathew_Miao | WA | 351ms | 53772kb | C++23 | 4.8kb | 2024-05-27 15:50:53 | 2024-05-27 15:50:54 |
Judging History
answer
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
const int N=2e5;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n;
struct node{
int x,y,id,typ;
};
inline bool operator <(node a,node b){
return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
}
inline bool cmp(node a,node b){
return (a.y<b.y)||(a.y==b.y&&a.typ>b.typ)||(a.y==b.y&&a.typ==b.typ&&a.x<b.x);
}
node a[MAXN],b[MAXN];
node p[MAXN*2];
int px[MAXN*2],py[MAXN*2];
inline void discrete(){
for(int i=1;i<=n;i++)
{
px[i]=a[i].x;
py[i]=a[i].y;
px[i+n]=b[i].x;
py[i+n]=b[i].y;
}
sort(px+1,px+1+n*2);
sort(py+1,py+1+n*2);
int totx=unique(px+1,px+1+n*2)-px-1;
int toty=unique(py+1,py+1+n*2)-py-1;
for(int i=1;i<=n;i++)
{
a[i].x=lower_bound(px+1,px+1+totx,a[i].x)-px-1;
a[i].y=lower_bound(py+1,py+1+toty,a[i].y)-py-1;
b[i].x=lower_bound(px+1,px+1+totx,b[i].x)-px-1;
b[i].y=lower_bound(py+1,py+1+toty,b[i].y)-py-1;
}
}
int mat[MAXN*2];
multiset <node> s;
#define ull unsigned long long
namespace segtree{
int L[MAXN*8],R[MAXN*8];
ull hsh[MAXN*8],tag[MAXN*8];
bool same[MAXN*8];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
inline void push_up(int x){
hsh[x]=hsh[ls(x)];
same[x]=same[ls(x)]&&same[rs(x)]&&(hsh[ls(x)]==hsh[rs(x)]);
}
inline void push_down(int x){
if(!tag[x]){
return ;
}
hsh[ls(x)]^=tag[x];
tag[ls(x)]^=tag[x];
hsh[rs(x)]^=tag[x];
tag[rs(x)]^=tag[x];
tag[x]=0;
}
void build(int l,int r,int x){
L[x]=l;
R[x]=r;
same[x]=true;
if(l==r){
return ;
}
int mid=(l+r)/2;
build(l,mid,ls(x));
build(mid+1,r,rs(x));
}
inline void build(){
build(1,n*2,1);
}
void modify(int ql,int qr,ull val,int x){
int l=L[x],r=R[x];
if(ql<=l&&r<=qr){
hsh[x]^=val;
tag[x]^=val;
return ;
}
if(r<ql||qr<l){
return ;
}
push_down(x);
modify(ql,qr,val,ls(x));
modify(ql,qr,val,rs(x));
push_up(x);
}
inline void modify(int ql,int qr,ull val){
modify(ql,qr,val,1);
}
ull lst;
bool fir;
bool query(int ql,int qr,int x){
int l=L[x],r=R[x];
if(ql<=l&&r<=qr){
if(!fir){
lst=hsh[x];
fir=true;
}
return same[x]&&(lst==hsh[x]);
}
if(r<ql||qr<l){
return true;
}
push_down(x);
return query(ql,qr,ls(x))&&query(ql,qr,rs(x));
}
inline bool query(int ql,int qr){
fir=false;
lst=0;
return query(ql,qr,1);
}
}
struct Qry{
int pos,l,r,add;
ull hsh;
}q[MAXN*2];
inline bool operator <(Qry x,Qry y){
if(x.pos^y.pos){
return x.pos<y.pos;
}
if(x.add^y.add){
return x.add<y.add;
}
if(~x.add){
return x.r-x.l>y.r-y.l;
}
else{
return x.r-x.l<y.r-y.l;
}
}
#include<random>
mt19937_64 rnd(372409);
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].typ=0;
a[i].id=i;
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&b[i].x,&b[i].y);
b[i].typ=1;
b[i].id=i;
}
discrete();
for(int i=1;i<=n;i++)
{
p[i]=a[i];
p[i+n]=b[i];
}
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n*2;i++)
{
if(!p[i].typ){
s.insert(p[i]);
}
else{
multiset <node>::iterator it=s.lower_bound(node{p[i].x-1,p[i].y,p[i].id,p[i].typ});
if(it==s.begin()){
puts("No");
return 0;
}
it--;
mat[it->id]=p[i].id;
s.erase(it);
}
}
segtree::build();
for(int i=1;i<=n;i++)
{
ull now=rnd();
q[i]=Qry{a[i].x,a[i].y,b[mat[i]].y,1,now};
q[i+n]=Qry{b[mat[i]].x,a[i].y,b[mat[i]].y,-1,now};
}
sort(q+1,q+1+n*2);
for(int i=1;i<=n*2;i++)
{
segtree::modify(q[i].l,q[i].r-1,q[i].hsh);
if(!segtree::query(q[i].l,q[i].r-1)){
puts("No");
exit(0);
}
}
puts("Yes");
for(int i=1;i<=n;i++)
{
printf("%d\n",mat[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22236kb
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: 0ms
memory: 22236kb
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: 13860kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 351ms
memory: 53772kb
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