Submission #1209735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209735		lighton	Card Collection (JOI24_collection)	C++20	71 / 100	4093 ms	124296 KiB

Main

#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];
map<pair<int,int>, vector<int> > mp;
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){
    return umax(umax(a,b.fs),b.se);
}
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(){
    forf(i,1,max(sz(X),sz(Y))) ins[i].clear(),qry[i].clear(),Apos[i].clear(),Bpos[i].clear();
    mp.clear();
    forf(i,1,N) mp[{A[i],B[i]}].pb(i);
    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]);

    forf(q,1,M){
        for(auto i : mp[{U[q],V[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(){
    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();
    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();
    forf(i,1,N) swap(A[i],B[i]);
    forf(i,1,M) swap(U[i],V[i]);
    swap(X,Y);
    solve();
    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();
    forf(i,1,M) if(ans[i]) cout<<i<< " ";
}

• Subtask 1: 11 / 11
• Subtask 2: 38 / 38
• Subtask 3: 22 / 22
• Subtask 4: 0 / 29