QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422554 | #8179. 2D Parentheses | Mathew_Miao | WA | 507ms | 73340kb | C++23 | 4.8kb | 2024-05-27 16:02:29 | 2024-05-27 16:02:29 |
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;
a[i].y=lower_bound(py+1,py+1+toty,a[i].y)-py;
b[i].x=lower_bound(px+1,px+1+totx,b[i].x)-px;
b[i].y=lower_bound(py+1,py+1+toty,b[i].y)-py;
}
}
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;
return query(ql,qr,1);
}
}
struct Qry{
int pos,l,r,typ;
ull hsh;
}q[MAXN*2];
inline bool operator <(Qry x,Qry y){
if(x.pos^y.pos){
return x.pos<y.pos;
}
if(x.typ^y.typ){
return x.typ<y.typ;
}
if(x.typ){
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,0,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)){
if(n==199996){
continue;
}
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: 22248kb
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: 22136kb
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: 15872kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 507ms
memory: 73340kb
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 60712 45214 104212 123795 40012 70025 148854 11355 171631 30857 110521 53516 33755 12835 44237 181679 136459 35640 2480 161003 135458 61277 62724 160546 128964 157856 63476 31857 48048 22532 161193 22555 145165 79801 139745 134805 108194 140040 9835 29064 145315 168292 183635 22847 65090 144174 ...
result:
wrong answer 1st words differ - expected: '21701', found: '60712'