QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424006 | #8179. 2D Parentheses | YMH_fourteen | WA | 1ms | 7660kb | C++14 | 3.0kb | 2024-05-28 20:44:23 | 2024-05-28 20:44:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "E:/OI/normal/templates/debug.h"
#else
#define dbg(...) (void)0
#define msg(...) (void)0
#endif
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second
const int N=200005;
int n;
struct poi
{
int x,y,id;
}lef[N],rig[N];
bool cmp1(poi &x,poi &y)
{
return x.y==y.y?x.x<y.x:x.y<y.y;
}
bool cmp2(poi &x,poi &y)
{
return x.x==y.x?x.y<y.y:x.x<y.x;
}
int ans[N];
struct op
{
int tim,l,r,typ,lst;
bool add;
bool operator<(const op &rhs)const
{
if(tim!=rhs.tim)return tim<rhs.tim;
if(add!=rhs.add)return add<rhs.add;// delete first
if(add)return r-l+1>rhs.r-rhs.l+1; // add larger ones first
return r-l+1<rhs.r-rhs.l+1; // remove smaller ones first
}
}f[N<<1];
struct cr
{
bool isr;
int cor,id;
bool operator<(const cr &rhs)const
{
if(cor!=rhs.cor)return cor<rhs.cor;
if(isr^rhs.isr)return isr;
if(isr)return id>rhs.id;
return id<rhs.id;
}
};
vector<cr>coor;
struct fajlkdjfklsad{bool operator()(poi x,poi y){return cmp2(x,y);}};
set<int>st2;
int tmp[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(nullptr);
// int _;cin>>_;while(_--)
cin>>n;
for(int i=1;i<=n;i++)cin>>lef[i].x>>lef[i].y,lef[i].id=i;
for(int i=1;i<=n;i++)cin>>rig[i].x>>rig[i].y,rig[i].id=i;
sort(lef+1,lef+n+1,cmp1);
sort(rig+1,rig+n+1,cmp1);
set<poi,fajlkdjfklsad>st;
for(int i=1,j=1;i<=n;i++)
{
while(j<=n&&lef[j].y<rig[i].y)st.insert(lef[j++]);
auto it=st.upper_bound(poi{rig[i].x-1,INT_MAX,-114514});
if(it==st.begin())return puts("No"),0;
it--;
ans[it->id]=rig[i].id;
f[2*i-1]={it->x,it->y,rig[i].y,i,1},f[2*i]={rig[i].x,it->y,rig[i].y,i,0};
st.erase(it);
}
sort(f+1,f+(n<<1)+1);
// for(int i=1;i<=n<<1;i++)cerr<<f[i].add<<" "<<f[i].l<<" "<<f[i].r<<endl;
for(int i=1;i<=n<<1;i++)
if(f[i].add)coor.PB(cr{0,f[i].l,i}),coor.PB(cr{1,f[i].r,i}),tmp[f[i].typ]=i;
sort(ALL(coor));
// for(auto i:coor)cerr<<i.isr<<" "<<i.cor<<" "<<i.id<<endl;
for(int i=1;i<=n<<1;i++)
f[i].l=lower_bound(ALL(coor),cr{0,f[i].l,tmp[f[i].typ]})-coor.begin()+1,
f[i].r=lower_bound(ALL(coor),cr{1,f[i].r,tmp[f[i].typ]})-coor.begin()+1;
// for(int i=1;i<=n<<1;i++)cerr<<f[i].add<<" "<<f[i].l<<" "<<f[i].r<<endl;
for(int i=1;i<=n<<1;i++)
if(f[i].add)
{
auto itl=st2.lower_bound(f[i].l),itr=st2.lower_bound(f[i].r);
if(itl!=itr)return puts("No"),0;
st2.insert(f[i].l),st2.insert(f[i].r);
}
else st2.erase(f[i].l),st2.erase(f[i].r);
// st.clear();
for(int i=n<<1;i;i--)
if(!f[i].add)
{
auto itl=st2.lower_bound(f[i].l),itr=st2.lower_bound(f[i].r);
if(itl!=itr)return puts("No"),0;
st2.insert(f[i].l),st2.insert(f[i].r);
}
else st2.erase(f[i].l),st2.erase(f[i].r);
cout<<"Yes\n";
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7648kb
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: -100
Wrong Answer
time: 1ms
memory: 7660kb
input:
2 1 0 0 1 2 3 3 2
output:
Yes 2 1
result:
wrong answer expected NO, found YES