QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423995 | #8179. 2D Parentheses | YMH_fourteen | WA | 456ms | 32872kb | C++14 | 3.0kb | 2024-05-28 20:38:30 | 2024-05-28 20:38:30 |
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;
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 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);
map<PII,int>g;
// 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}),g[MP(f[i].l,f[i].r)]=i;
sort(ALL(coor));
// for(auto i:coor)cerr<<i.isr<<" "<<i.cor<<" "<<i.id<<endl;
for(int i=1,t;t=f[i].l,i<=n<<1;i++)
f[i].l=lower_bound(ALL(coor),cr{0,f[i].l,g[MP(f[i].l,f[i].r)]})-coor.begin()+1,
f[i].r=lower_bound(ALL(coor),cr{1,f[i].r,g[MP(t,f[i].r)]})-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: 1ms
memory: 3708kb
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: 3840kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 456ms
memory: 32872kb
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