Submission #1209741

#TimeUsernameProblemLanguageResultExecution timeMemory
1209741lightonCard Collection (JOI24_collection)C++20
71 / 100
4080 ms123132 KiB
#include<bits/stdc++.h> #define pb push_back #define all(v) v.begin(),v.end() #define forf(i,s,e) for(int i = s; i<=e; i++) #define forb(i,s,e) for(int i = s; i>=e; i--) #define idx(i,v) lower_bound(all(v),i)-v.begin() #define comp(v) v.erase(unique(all(v)),v.end()) #define sz(v) (int)v.size() #define fs first #define se second #define SP << " " << #define LN << "\n" #define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false); using namespace std; typedef long long ll; int inf = 2e9; int N,M; int A[200001],B[200001]; int U[200001],V[200001]; vector<int> X,Y; int pA[2][200005], sA[2][200005], pB[2][200005], sB[2][200005]; unordered_map<ll, vector<int> > mp; unordered_map<ll, int > mp2; vector<int> Apos[400001], Bpos[400001]; int ans[200001]; pair<int,int> umax(pair<int,int> a, int x){ if(x > a.fs) return {x,a.fs}; if(x > a.se) return {a.fs,x}; else return a; } pair<int,int> mmax(pair<int,int> a, pair<int,int> b){ if(a.fs < b.fs) swap(a,b); if(b.fs > a.se) return {a.fs, b.fs}; else return a; } struct Seg{ pair<int,int> arr[4000001]; void init(int n){ fill(arr,arr+4*n,pair<int,int>{-inf,-inf}); } void update(int now, int s, int e, int f, int x){ if(s==e){ arr[now] = umax(arr[now],x); return; } int m = s+e>>1; if(f<=m) update(now*2,s,m,f,x); else update(now*2+1,m+1,e,f,x); arr[now] = mmax(arr[now*2],arr[now*2+1]); } pair<int,int> query(int now, int s, int e, int l, int r){ if(l>r) return {-inf,-inf}; if(l<=s && e<=r) return arr[now]; if(l>e || r<s) return {-inf,-inf}; int m = s+e>>1; return mmax(query(now*2,s,m,l,r) , query(now*2+1,m+1,e,l,r)); } } seg; vector<pair<int,int> > ins[400001], qry[400001]; int S[200001], E[200001]; void solve(int fuck){ forf(i,1,max(sz(X),sz(Y))) ins[i].clear(),qry[i].clear(),Apos[i].clear(),Bpos[i].clear(); mp.clear(); pA[0][0] = pB[0][0] = sA[0][N+1] = sB[0][N+1] = inf; pA[1][0] = pB[1][0] = sA[1][N+1] = sB[1][N+1] = -inf; forf(i,1,N) pA[0][i] = min(pA[0][i-1], A[i]), pB[0][i] = min(pB[0][i-1], B[i]), pA[1][i] = max(pA[1][i-1], A[i]), pB[1][i] = max(pB[1][i-1], B[i]); forb(i,N,1) sA[0][i] = min(sA[0][i+1], A[i]), sB[0][i] = min(sB[0][i+1], B[i]), sA[1][i] = max(sA[1][i+1], A[i]), sB[1][i] = max(sB[1][i+1], B[i]); if(fuck == 1) { forf(i, 1, N) mp[A[i] * (ll) inf + B[i]].pb(i); forf(q, 1, M) { if(mp2[U[q] * (ll) inf + V[q]] && ans[mp2[U[q] * (ll) inf + V[q]]] == 1) ans[q] = 1; for (auto i: mp[U[q] * (ll) inf + V[q]]) { mp2[U[q] * (ll) inf + V[q]] = q; int c = 1; if (i != 1 && ((pA[1][i - 1] < U[q] && pB[0][i - 1] > V[q]) || (pA[0][i - 1] > U[q] && pB[1][i - 1] < V[q]))) c = 0; if (i != N && ((sA[1][i + 1] < U[q] && sB[0][i + 1] > V[q]) || (sA[0][i + 1] > U[q] && sB[1][i + 1] < V[q]))) c = 0; if (c) ans[q] = 1; } } } forf(i,1,N) ins[A[i]].pb({B[i],i}); forf(i,1,M) qry[U[i]].pb({V[i],i}); forf(i,1,N) Apos[A[i]].pb(i), Bpos[B[i]].pb(i); forf(i,1,M){ if(sz(Apos[U[i]])) S[i] = Apos[U[i]][0]; else S[i] = N+1; if(sz(Bpos[V[i]])) E[i] = Bpos[V[i]].back(); else E[i] = 0; } seg.init(sz(Y)); forf(i,1,sz(X)){ for(auto [x,k] : ins[i]) seg.update(1,1,sz(Y),x,-k); for(auto [x,k] : qry[i]){ auto tmp = seg.query(1,1,sz(Y),x,sz(Y)); tmp.fs *= -1, tmp.se *= -1; if(tmp.fs > N) S[k] = max(S[k], tmp.fs); else if(tmp.fs != 1 && pA[0][tmp.fs-1] > U[k] && pB[1][tmp.fs-1] < V[k]) S[k] = max(S[k], tmp.se); else S[k] = max(S[k],tmp.fs); } } seg.init(sz(Y)); forb(i,sz(X),1){ for(auto [x,k] : ins[i]) seg.update(1,1,sz(Y),x,k); for(auto [x,k] : qry[i]){ auto tmp = seg.query(1,1,sz(Y),1,x); if(tmp.fs <= 0) E[k] = min(E[k], tmp.fs); else if(tmp.fs != N && sA[1][tmp.fs+1] < U[k] && sB[0][tmp.fs+1] > V[k]) E[k] = min(E[k], tmp.se); else E[k] = min(E[k],tmp.fs); } } forf(i,1,M) if(S[i]<E[i]) ans[i] = 1; } int main(){ IO cin>>N>>M; forf(i,1,N) cin>>A[i]>>B[i], X.pb(A[i]), Y.pb(B[i]); forf(i,1,M) cin>>U[i]>>V[i], X.pb(U[i]), Y.pb(V[i]); sort(all(X)), sort(all(Y)), comp(X), comp(Y); forf(i,1,N) A[i] = idx(A[i],X)+1, B[i] = idx(B[i], Y)+1; forf(i,1,M) U[i] = idx(U[i], X)+1, V[i] = idx(V[i],Y)+1; solve(1); forf(i,1,N) A[i] = sz(X)-A[i]+1, B[i] = sz(Y)-B[i]+1; forf(i,1,M) U[i] = sz(X)-U[i]+1, V[i] = sz(Y)-V[i]+1; solve(0); forf(i,1,N) swap(A[i],B[i]); forf(i,1,M) swap(U[i],V[i]); swap(X,Y); solve(0); forf(i,1,N) A[i] = sz(X)-A[i]+1, B[i] = sz(Y)-B[i]+1; forf(i,1,M) U[i] = sz(X)-U[i]+1, V[i] = sz(Y)-V[i]+1; solve(0); forf(i,1,M) if(ans[i]) cout<<i<< " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...