제출 #1142473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142473		Math4Life2020	새 집 (APIO18_new_home)	C++20	47 / 100	5121 ms	835120 KiB

new_home

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

map<ll,ll> st1[2*Nm]; //store C in x+C
map<ll,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())));
        // }
        while (!st1[(y>>e)+(1<<(E-e))].empty()) {
            auto A1 = --st1[(y>>e)+(1<<(E-e))].end();
            if ((*A1).second>0) {
                fval = max(fval,x+(*A1).first);
                break;
            } else {
                st1[(y>>e)+(1<<(E-e))].erase(A1);
            }
        }
        while (!st2[(y>>e)+(1<<(E-e))].empty()) {
            auto A1 = --st2[(y>>e)+(1<<(E-e))].end();
            if ((*A1).second>0) {
                fval = max(fval,-x+(*A1).first);
                break;
            } else {
                st2[(y>>e)+(1<<(E-e))].erase(A1);
            }
        }
    }
    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][v]++;
        ins1(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st1[p][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][v]++;
        ins2(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st2[p][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][v]--;
        del1(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st1[p][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][v]--;
        del2(a+(1<<va),b,v);
    } else {
        ll p = (b>>vb)+(1<<(E-vb));
        st2[p][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