Submission #1150362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150362		vladilius	새 집 (APIO18_new_home)	C++17	57 / 100	5093 ms	325608 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int inf = 1e8;
const int inff = inf + 1;
const int N = 2e6;
 
struct IT{
    struct node{
        int m1, m2, i, l, r;
        node(){
            l = r = 0;
            m1 = inff; m2 = 0;
        }
    };
    multiset<int> s[N];
    vector<node> all;
    int cc, cc1;
    void init(){
        all.pb(node());
        all.pb(node());
        cc = 1; cc1 = 0;
    }
    int nw(int tl, int tr){
        all.pb(node()); cc++;
        if (tl == tr){
            cc1++;
            all[cc].i = cc1;
        }
        return cc;
    }
    void add2(int p, int x){
        int tl = 1, tr = inf, v = 1;
        while (tl != tr){
            all[v].m2 = max(all[v].m2, x);
            int tm = (tl + tr) / 2;
            if (p <= tm){
                if (!all[v].l) all[v].l = nw(tl, tm);
                tr = tm;
                v = all[v].l;
            }
            else {
                if (!all[v].r) all[v].r = nw(tm + 1, tr);
                tl = tm + 1;
                v = all[v].r;
            }
        }
        s[all[v].i].insert(x);
        all[v].m2 = max(all[v].m2, x);
    }
    void add1(int p, int x){
        int tl = 1, tr = inf, v = 1;
        while (tl != tr){
            all[v].m1 = min(all[v].m1, x);
            int tm = (tl + tr) / 2;
            if (p <= tm){
                if (!all[v].l) all[v].l = nw(tl, tm);
                tr = tm;
                v = all[v].l;
            }
            else {
                if (!all[v].r) all[v].r = nw(tm + 1, tr);
                tl = tm + 1;
                v = all[v].r;
            }
        }
        s[all[v].i].insert(x);
        all[v].m1 = min(all[v].m1, x);
    }
    void add(int l, int r){
        if (l == 1){
            add2(l, r + 1);
            return;
        }
        if (r == inf){
            add1(inf, l - 1);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) add1(m, l - 1);
        if (m < r) add2(m + 1, r + 1);
    }
    vector<int> f;
    void rem2(int p, int x){
        f.clear();
        int tl = 1, tr = inf, v = 1;
        while (tl != tr){
            f.pb(v);
            int tm = (tl + tr) / 2;
            if (p <= tm){
                tr = tm;
                v = all[v].l;
            }
            else {
                tl = tm + 1;
                v = all[v].r;
            }
        }
        s[all[v].i].erase(s[all[v].i].find(x));
        all[v].m2 = s[all[v].i].empty() ? 0 : *prev(s[all[v].i].end());

        for (int i = f.size() - 1; i >= 0; i--){
            all[f[i]].m2 = 0;
            if (all[f[i]].l) all[f[i]].m2 = max(all[f[i]].m2, all[all[f[i]].l].m2);
            if (all[f[i]].r) all[f[i]].m2 = max(all[f[i]].m2, all[all[f[i]].r].m2);
        }
    }
    void rem1(int p, int x){
        f.clear();
        int tl = 1, tr = inf, v = 1;
        while (tl != tr){
            f.pb(v);
            int tm = (tl + tr) / 2;
            if (p <= tm){
                tr = tm;
                v = all[v].l;
            }
            else {
                tl = tm + 1;
                v = all[v].r;
            }
        }
        s[all[v].i].erase(s[all[v].i].find(x));
        all[v].m1 = s[all[v].i].empty() ? inff : *s[all[v].i].begin();

        for (int i = f.size() - 1; i >= 0; i--){
            v = f[i];
            all[v].m1 = inff;
            if (all[v].l) all[v].m1 = min(all[v].m1, all[all[v].l].m1);
            if (all[v].r) all[v].m1 = min(all[v].m1, all[all[v].r].m1);
        }
    }
    void rem(int l, int r){
        if (l == 1){
            rem2(l, r + 1);
            return;
        }
        if (r == inf){
            rem1(inf, l - 1);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) rem1(m, l - 1);
        if (m < r) rem2(m + 1, r + 1);
    }
    int get2(int v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return all[v].m2;
        int tm = (tl + tr) / 2, out = 0;
        if (all[v].l){
            out = max(out, get2(all[v].l, tl, tm, l, r));
        }
        if (all[v].r){
            out = max(out, get2(all[v].r, tm + 1, tr, l, r));
        }
        return out;
    }
    int get1(int v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return inff;
        if (l <= tl && tr <= r) return all[v].m1;
        int tm = (tl + tr) / 2, out = inff;
        if (all[v].l){
            out = min(out, get1(all[v].l, tl, tm, l, r));
        }
        if (all[v].r){
            out = min(out, get1(all[v].r, tm + 1, tr, l, r));
        }
        return out;
    }
    pii get(int x){
        return {get1(1, 1, inf, x, inf), get2(1, 1, inf, 1, x)};
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k, q; cin>>n>>k>>q;
    vector<int> x(n + 1), t(n + 1), a(n + 1), b(n + 1);
    bool ind = 1;
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
        if (a[i] != 1) ind = 0;
    }
    vector<int> xq(q + 1), yq(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>xq[i]>>yq[i];
    }
 
    vector<int> out(q + 1), cnt(k + 1);
    multiset<int> st[k + 1];
    int df = 0, l, r;
    IT T; T.init();
    vector<arr3> mp;
    if (!ind){
        for (int i = 1; i <= n; i++){
            mp.pb({a[i], 1, i});
            if (b[i] < inf) mp.pb({b[i] + 1, 2, i});
        }
        for (int i = 1; i <= q; i++){
            mp.pb({yq[i], i + 2, xq[i]});
        }
    }
    else {
        vector<int> f[k + 1];
        for (int i = 1; i <= n; i++) f[t[i]].pb(x[i]);
        for (int i = 1; i <= k; i++){
            if (f[i].empty()) continue;
            sort(f[i].begin(), f[i].end());
            int pre = 1;
            for (int j: f[i]){
                if (pre < j){
                    T.add(pre, j - 1);
                }
                pre = j + 1;
            }
            if (pre <= inf) T.add(pre, inf);
        }
        for (int i = 1; i <= n; i++){
            df += !cnt[t[i]]; cnt[t[i]]++;
            st[t[i]].insert(x[i]);
            if (b[i] < inf) mp.pb({b[i] + 1, 2, i});
        }
        for (int i = 1; i <= q; i++){
            mp.pb({yq[i], i + 2, xq[i]});
        }
    }
    
    auto cmp = [&](arr3 x, arr3 y){
        if (x[0] == y[0]){
            return x[1] < y[1];
        }
        return x[0] < y[0];
    };
    
    sort(mp.begin(), mp.end(), cmp);
    
    for (auto [X, tt, i]: mp){
        if (tt == 1){
            df += !cnt[t[i]];
            cnt[t[i]]++;
            if (cnt[t[i]] == 1){
                if (1 < x[i]) T.add(1, x[i] - 1);
                if (x[i] < inf) T.add(x[i] + 1, inf);
                st[t[i]].insert(x[i]);
                continue;
            }
            if (st[t[i]].find(x[i]) != st[t[i]].end()){
                st[t[i]].insert(x[i]);
                continue;
            }
            
            auto it = st[t[i]].upper_bound(x[i]);
            if (it == st[t[i]].end()) r = inf;
            else r = (*it) - 1;
            if (it == st[t[i]].begin()) l = 1;
            else l = *prev(it) + 1;
            
            if (l <= r) T.rem(l, r);
            if (l < x[i]) T.add(l, x[i] - 1);
            if (x[i] < r) T.add(x[i] + 1, r);
            
            st[t[i]].insert(x[i]);
        }
        else if (tt == 2){
            cnt[t[i]]--;
            df -= !cnt[t[i]];
            
            if (st[t[i]].count(x[i]) > 1){
                st[t[i]].erase(st[t[i]].find(x[i]));
                continue;
            }
            
            auto it = st[t[i]].find(x[i]);
            
            if (it == st[t[i]].begin()) l = 1;
            else l = *prev(it) + 1;
            if (it == prev(st[t[i]].end())) r = inf;
            else r = *next(it) - 1;
            
            if (l < x[i]) T.rem(l, x[i] - 1);
            if (x[i] < r) T.rem(x[i] + 1, r);
            
            if (cnt[t[i]]) T.add(l, r);
            st[t[i]].erase(it);
        }
        else {
            int ii = tt - 2;
            if (df < k){
                out[ii] = -1;
                continue;
            }
            
            auto [l, r] = T.get(i);
            if (l != inff) out[ii] = max(out[ii], i - l);
            if (r != 0) out[ii] = max(out[ii], r - i);
        }
    }
    
    for (int i = 1; i <= q; i++){
        cout<<out[i]<<"\n";
    }
}

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