제출 #1142405

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

new_home

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N,K,Q;
const ll Nm = 32; const ll E = 5;
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++) {
        //cout << "check: "<<((y>>e)+(1<<(E-e)))<<"\n";
        if (!st1[(y>>e)+(1<<(E-e))].empty()) {
            //cout << "f3\n";
            fval = max(fval,x+*(prev(st1[(y>>e)+(1<<(E-e))].end())));
        }
        if (!st2[(y>>e)+(1<<(E-e))].empty()) {
            //cout << "f4\n";
            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) { //insert to [a,b) -> aka NOT my standard template
//     if (a>=b) {
//         return;
//     }
//     ll va = v2(a); ll vb = v2(b);
//     if (va<vb) {
//         cout << "calling ins1: "<<((a>>va)+(1<<(E-va)))<<"\n";
//         st1[(a>>va)+(1<<(E-va))].insert(v);
//         ins1(a+(1<<va),b,v);
//     } else {
//         cout << "calling ins1: "<<((b>>vb)+(1<<(E-vb)))<<"\n";
//         st1[(b>>vb)+(1<<(E-vb))].insert(v);
//         ins1(a,b-(1<<vb),v);
//     }
// }

// void ins2(ll a, ll b, ll v) { //insert to [a,b) -> aka NOT my standard template
//     if (a>=b) {
//         return;
//     }
//     ll va = v2(a); ll vb = v2(b);
//     if (va<vb) {
//         cout << "calling ins2: "<<((a>>va)+(1<<(E-va)))<<"\n";
//         st2[(a>>va)+(1<<(E-va))].insert(v);
//         ins2(a+(1<<va),b,v);
//     } else {
//         cout << "calling ins2: "<<((b>>vb)+(1<<(E-vb)))<<"\n";
//         st2[(b>>vb)+(1<<(E-vb))].insert(v);
//         ins2(a,b-(1<<vb),v);
//     }
// }

// void del1(ll a, ll b, ll v) { //erase from [a,b) -> aka NOT my standard template
//     if (a>=b) {
//         return;
//     }
//     ll va = v2(a); ll vb = v2(b);
//     if (va<vb) {
//         cout << "calling del1: "<<((a>>va)+(1<<(E-va)))<<"\n";
//         assert(st1[(a>>va)+(1<<(E-va))].find(v)!= st1[(a>>va)+(1<<(E-va))].end());
//         st1[(a>>va)+(1<<(E-va))].erase(st1[(a>>va)+(1<<(E-va))].find(v));
//         del1(a+(1<<va),b,v);
//     } else {
//         cout << "calling del1: "<<((b>>vb)+(1<<(E-vb)))<<"\n";
//         assert(st1[(b>>vb)+(1<<(E-vb))].find(v)!=st1[(b>>vb)+(1<<(E-vb))].end());
//         st1[(b>>vb)+(1<<(E-vb))].erase(st1[(b>>vb)+(1<<(E-vb))].find(v));
//         del1(a,b-(1<<vb),v);
//     }
// }

// void del2(ll a, ll b, ll v) { //insert to [a,b) -> aka NOT my standard template
//     if (a>=b) {
//         return;
//     }
//     ll va = v2(a); ll vb = v2(b);
//     if (va<vb) {
//         cout << "calling del2: "<<((a>>va)+(1<<(E-va)))<<"\n";
//         assert(st2[(a>>va)+(1<<(E-va))].find(v)!=st2[(a>>va)+(1<<(E-va))].end());
//         st2[(a>>va)+(1<<(E-va))].erase(st2[(a>>va)+(1<<(E-va))].find(v));
//         del2(a+(1<<va),b,v);
//     } else {
//         cout << "calling del2: "<<((b>>vb)+(1<<(E-vb)))<<"\n";
//         assert(st2[(b>>vb)+(1<<(E-vb))].find(v)!=st2[(b>>vb)+(1<<(E-vb))].end());
//         st2[(b>>vb)+(1<<(E-vb))].erase(st2[(b>>vb)+(1<<(E-vb))].find(v));
//         del2(a,b-(1<<vb),v);
//     }
// }

// void ins(ll a, ll b) {
//     cout << "insert a,b="<<a<<","<<b<<"\n";
//     ll ya = cvrt[a];
//     ll ym = cvrt[(a+b+1)/2];
//     ll yb = cvrt[b];
//     cout << "ya,ym,yb="<<ya<<","<<ym<<","<<yb<<"\n";
//     ins1(ya,ym,-a);
//     ins2(ym,yb,b);
// }

// void del(ll a, ll b) {
//     cout << "delete a,b="<<a<<","<<b<<"\n";
//     ll ya = cvrt[a];
//     ll ym = cvrt[(a+b+1)/2];
//     ll yb = cvrt[b];
//     cout << "ya,ym,yb="<<ya<<","<<ym<<","<<yb<<"\n";
//     del1(ya,ym,-a);
//     del2(ym,yb,b);
// }

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) {
    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) {
    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--;
        a--; b--;
        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);
                sx.insert((x+(*prev(A1)).first+1)/2);
                sx.insert((x+(*next(A1)).first+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);
                sx.insert(((*prev(A1)).first+(*next(A1)).first+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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20