QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422973 | #8179. 2D Parentheses | qwqwf | Compile Error | / | / | C++14 | 1.4kb | 2024-05-27 20:37:38 | 2024-05-27 20:37:39 |
Judging History
answer
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
#define pii pair<int,int>
#define MP make_pair
#define fi first
#define se second
using namespace std;
const int N=5e5+10,M=1e6+10,mod=998244353;
int n,X[N],Y[N];
int ans[N];
int p[N];
set<pii> st;
multiset<int> s;
inline bool cmp(int a,int b){return X[a]!=X[b]?X[a]>X[b]:Y[a]>Y[b];}
bool solve(){
for(int i=0;i<2*n;i++) p[i]=i;
sort(p,p+2*n,cmp);
for(int i=0;i<2*n;i++){
int v=p[i];
if(v<n){
auto w=st.lower_bound(MP(Y[v],0));
if(w==st.end()) return 0;
int t=(*w).se;
ans[v]=t;ans[t]=v;
st.erase(w);
}
else st.insert(MP(Y[v],v));
}
for(int i=0;i<2*n;i++){
int u=p[i],v=ans[u];
if(u<n) s.erase(s.find(Y[u])),s.erase(s.find(Y[v]));
else{
if(Y[u]<Y[v]) swap(u,v);
auto w=s.lower_bound(Y[u]);
if(w!=s.begin()){
--w;
if((*w)>Y[v]) return 0;
}
s.insert(Y[u]);s.insert(Y[v]);
}
}
return 1;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;i++) cin>>X[i]>>Y[i],X[i]*=2,Y[i]*=2;
for(int i=n;i<2*n;i++)cin>>X[i]>>Y[i],X[i]*=2,Y[i]*=2,X[i]--,Y[i]--;
if(!solve()) return cout<<"No\n",0;
else{
cout<<"Yes\n";
for(int i=0;i<n;i++) cout<<ans[i]-n+1<<'\n';
}
return 0;
}
Details
In file included from /usr/include/c++/13/string:43, from /usr/include/c++/13/bitset:52, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52, from answer.code:3: /usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_Rb_tree_impl<std::less<std::pair<int, int> >, true>::~_Rb_tree_impl()’: /usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<std::pair<int, int> >]’: target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /usr/include/c++/13/map:62, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152: /usr/include/c++/13/bits/stl_tree.h:662:16: note: called from here 662 | struct _Rb_tree_impl | ^~~~~~~~~~~~~