Submission #1142465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142465		Math4Life2020	새 집 (APIO18_new_home)	C++20	47 / 100	5036 ms	610332 KiB

new_home

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N,K,Q;
const ll Nm = (1LL<<19); const ll E = 19;
const ll INF = 1e10;
ll ans[Nm];

multiset<ll> st1[2*Nm]; //store C in x+C
multiset<ll> st2[2*Nm]; //store C in -x+C

map<ll,ll> cvrt;

ll qry(ll x) {
    auto A0 = --cvrt.upper_bound(x);
    ll y = (*A0).second;
    ll fval = -INF;
    for (ll e=0;e<E;e++) {
        if (!st1[(y>>e)+(1<<(E-e))].empty()) {
            fval = max(fval,x+*(prev(st1[(y>>e)+(1<<(E-e))].end())));
        }
        if (!st2[(y>>e)+(1<<(E-e))].empty()) {
            fval = max(fval,-x+*(prev(st2[(y>>e)+(1<<(E-e))].end())));
        }
    }
    return fval;
}

inline ll v2(ll x) {
    return __builtin_ctz(x);
}

void ins1(ll a, ll b, ll v) {
    if (a>b) {
        return;
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        ll p = (a>>va)+(1<<(E-va));
        st1[p].insert(v);
        ins1(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st1[p].insert(v);
        ins1(a,b-(1<<vb),v);
    }
}

void ins2(ll a, ll b, ll v) {
    if (a>b) {
        return;
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        ll p = (a>>va)+(1<<(E-va));
        st2[p].insert(v);
        ins2(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st2[p].insert(v);
        ins2(a,b-(1<<vb),v);
    }
}

void del1(ll a, ll b, ll v) {
    if (a>b) {
        return;
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        ll p = (a>>va)+(1<<(E-va));
        st1[p].erase(st1[p].find(v));
        del1(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st1[p].erase(st1[p].find(v));
        del1(a,b-(1<<vb),v);
    }
}

void del2(ll a, ll b, ll v) {
    if (a>b) {
        return;
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        ll p = (a>>va)+(1<<(E-va));
        st2[p].erase(st2[p].find(v));
        del2(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st2[p].erase(st2[p].find(v));
        del2(a,b-(1<<vb),v);
    }
}

void ins(ll a, ll b) {
    if (a==-INF) {
        ins2(cvrt[a],cvrt[b],b);
        return;
    }
    if (b==INF) {
        ins1(cvrt[a],cvrt[b],-a);
        return;
    }
    ll ya = cvrt[a];
    ll ym = cvrt[(a+b+1)/2];
    ll yb = cvrt[b];
    ins1(ya,ym-1,-a);
    ins2(ym,yb-1,b);
}

void del(ll a, ll b) {
    if (a==-INF) {
        del2(cvrt[a],cvrt[b],b);
        return;
    }
    if (b==INF) {
        del1(cvrt[a],cvrt[b],-a);
        return;
    }
    ll ya = cvrt[a];
    ll ym = cvrt[(a+b+1)/2];
    ll yb = cvrt[b];
    del1(ya,ym-1,-a);
    del2(ym,yb-1,b);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> K >> Q;
    map<ll,ll> m0[K];
    vector<array<ll,4>> upd;
    set<ll> sx;
    for (ll i=0;i<N;i++) {
        ll x,t,a,b; cin >> x >> t >> a >> b;
        t--;
        upd.push_back({a,1,x,t});
        upd.push_back({b+1,2,x,t});
    }
    for (ll q=0;q<Q;q++) {
        ll l,y; cin >> l >> y;
        upd.push_back({y,3,l,q});
    }
    for (ll k=0;k<K;k++) {
        m0[k][-INF]=1;
        m0[k][INF]=1;
    }
    sort(upd.begin(),upd.end());
    sx.insert(-INF);
    sx.insert(INF);
    for (auto A0: upd) {
        //cout << "A0: "<<A0[0]<<", "<<A0[1]<<", "<<A0[2]<<", "<<A0[3]<<"\n"; 
        //continue;
        if (A0[1]==1) {
            ll t = A0[3];
            ll x = A0[2];
            sx.insert(x);
            if (m0[t].find(x)==m0[t].end()) {
                m0[t][x]=1;
                auto A1 = m0[t].find(x);
                ll P0 = (*prev(A1)).first;
                ll N0 = (*next(A1)).first;
                if (P0 != -INF) {
                    sx.insert((x+P0+1)/2);
                }
                if (N0 != INF) {
                    sx.insert((x+N0+1)/2);
                }
            } else {
                m0[t][x]++;
            }
        } else if (A0[1]==2) {
            ll t = A0[3];
            ll x = A0[2];
            assert(m0[t].find(x)!=m0[t].end());
            if (m0[t][x]==1) {
                auto A1 = m0[t].find(x);
                ll P0 = (*prev(A1)).first;
                ll N0 = (*next(A1)).first;
                if (P0 != -INF && N0 != INF) {
                    sx.insert((P0+N0+1)/2);
                }
                m0[t].erase(m0[t].find(x));
            } else {
                m0[t][x]--;
            }
        }
    }
    ll icv = 0;
    for (ll x: sx) {
        //cout << "x in sx="<<x<<"\n";
        cvrt[x]=(icv++);
    }
    for (ll k=0;k<K;k++) {
        m0[k].clear();
        m0[k][-INF]=1;
        m0[k][INF]=1;
        ins(-INF,INF);
    }
    ll NACT = 0;
    //exit(0);
    for (auto A0: upd) {
        //cout << "A0: "<<A0[0]<<", "<<A0[1]<<", "<<A0[2]<<", "<<A0[3]<<"\n"; 
        if (A0[1]==1) {
            ll t = A0[3];
            ll x = A0[2];
            if (m0[t].size()==2) {
                NACT++;
            }
            if (m0[t].find(x)==m0[t].end()) {
                m0[t][x]=1;
                auto A1 = m0[t].find(x);
                del((*prev(A1)).first,(*next(A1)).first);
                ins((*prev(A1)).first,x);
                ins(x,(*next(A1)).first);
            } else {
                m0[t][x]++;
            }
        } else if (A0[1]==2) {
            ll t = A0[3];
            ll x = A0[2];
            if (m0[t][x]==1) {
                auto A1 = m0[t].find(x);
                ins((*prev(A1)).first,(*next(A1)).first);
                del((*prev(A1)).first,x);
                del(x,(*next(A1)).first);
                m0[t].erase(m0[t].find(x));
                if (m0[t].size()==2) {
                    NACT--;
                }
            } else {
                m0[t][x]--;
            }
        } else {
            if (NACT<K) {
                ans[A0[3]]=-1;
            } else {
                ans[A0[3]]=qry(A0[2]);
            }
        }
    }
    for (ll i=0;i<Q;i++) {
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20