Submission #1259190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259190		antonn	New Home (APIO18_new_home)	C++20	80 / 100	5111 ms	516256 KiB

new_home

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5 + 7;

int n, k, q;
int x[N], t[N], a[N], b[N], l[N], y[N];
int sol[N];
map<int, int> idT, idX;
vector<int> revT, revX;
int szX;

int get_split(int l, int r) {
    int low = l, high = r, sol = l;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (revX[mid] - revX[l] <= revX[r] - revX[mid]) {
            sol = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return sol;
}

struct STMin { 
    vector<int> t;
    int Time;
    vector<array<int, 3>> stk;
    int n;
    
    void init(int nn) {
        n = nn;
        Time = 0;
        t.assign(4 * n + 1, 1e9);
    }
    
    void update(int v, int tl, int tr, int l, int r, int x) {
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r) {           
            stk.push_back({Time, v, t[v]});
            t[v] = min(t[v], x);
            return;
        }
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, r, x);
        update(2 * v + 1, tm + 1, tr, l, r, x);
    }
    
    void ckmin(int l, int r, int x) {
        if (l > r) return;
        update(1, 1, n, l, r, x);
    }
    
    int get(int v, int tl, int tr, int p) {
        if (tl == tr) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        if (p <= tm) {
            return min(t[v], get(2 * v, tl, tm, p));
        } else {
            return min(t[v], get(2 * v + 1, tm + 1, tr, p));
        }
    }
    
    int get(int p) {
        return get(1, 1, n, p);
    }
    
    void undo(int x) {
        while (!stk.empty() && stk.back()[0] > x) {
            t[stk.back()[1]] = stk.back()[2];
            stk.pop_back();
        }
    }
};

struct STMax { 
    vector<int> t;
    int Time;
    vector<array<int, 3>> stk;
    int n;
    
    void init(int nn) {
        n = nn;
        Time = 0;
        t.assign(4 * n + 1, 0);
    }
    
    void update(int v, int tl, int tr, int l, int r, int x) {
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r) {
            stk.push_back({Time, v, t[v]});
            t[v] = max(t[v], x);
            return;
        }
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, r, x);
        update(2 * v + 1, tm + 1, tr, l, r, x);
    }
    
    void ckmax(int l, int r, int x) {
        if (l > r) return;
        update(1, 1, n, l, r, x);
    }
    
    int get(int v, int tl, int tr, int p) {
        if (tl == tr) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        if (p <= tm) {
            return max(t[v], get(2 * v, tl, tm, p));
        } else {
            return max(t[v], get(2 * v + 1, tm + 1, tr, p));
        }
    }
    
    int get(int p) {
        return get(1, 1, n, p);
    }
    
    void undo(int x) {
        while (!stk.empty() && stk.back()[0] > x) {
            t[stk.back()[1]] = stk.back()[2];
            stk.pop_back();
        }
    }
};

STMin tmin;
STMax tmax;
vector<pair<int, int>> qs[12 * N], updates[12 * N];

void add_queries(int v, int tl, int tr, int p, int x, int id) {
    if (tl == tr) {
        qs[v].push_back({x, id});
    } else {
        int tm = (tl + tr) / 2;
        if (p <= tm) {
            add_queries(2 * v, tl, tm, p, x, id);
        } else {
            add_queries(2 * v + 1, tm + 1, tr, p, x, id);
        }
    }
}

void add_rem(int v, int tl, int tr, int l, int r, int x, int t) {
    if (l > tr || r < tl || l > r) return;
    if (l <= tl && tr <= r) {
        updates[v].push_back({x, t});
        return;
    }
    int tm = (tl + tr) / 2;
    add_rem(2 * v, tl, tm, l, r, x, t);
    add_rem(2 * v + 1, tm + 1, tr, l, r, x, t);
}

multiset<int> s[N];
int f[N], cnt = 0;

void solve(int v, int tl, int tr) {
    int time_min = tmin.Time;
    int time_max = tmax.Time;
    tmin.Time++;
    tmax.Time++;
    for (auto [x, t] : updates[v]) {
        f[t]--;
        if (f[t] == 0) cnt--;
        auto it = s[t].find(x);
        if (it == s[t].begin()) {
            if (next(it) == s[t].end()) {
                tmax.ckmax(1, szX, 1e9);
            } else {
                tmax.ckmax(1, *next(it), revX[*next(it)]);
            }
        } else if (next(it) == s[t].end()) {
            if (it == s[t].begin()) {
                tmin.ckmin(1, szX, -1e9);
            } else {
                tmin.ckmin(*prev(it), szX, revX[*prev(it)]);
            }
        } else {
            int a = *prev(it);
            int b = *it;
            int c = *next(it);
            int mid = get_split(a, c);
            tmin.ckmin(a, mid, revX[a]);
            tmax.ckmax(mid + 1, c, revX[c]);
        }
        s[t].erase(it);
    }
    if (tl == tr) {
        for (auto [x, id] : qs[v]) {
            if (cnt < k) {
                sol[id] = -1;
            } else {
                sol[id] = max(revX[x] - tmin.get(x), tmax.get(x) - revX[x]);
            }
        }
    } else {
        int tm = (tl + tr) / 2;
        solve(2 * v, tl, tm);
        solve(2 * v + 1, tm + 1, tr);
    }
    tmin.undo(time_min);
    tmax.undo(time_max);
    for (auto [x, t] : updates[v]) {
        f[t]++;
        if (f[t] == 1) cnt++;
        s[t].insert(x);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
    }
    for (int i = 1; i <= q; ++i) {
        cin >> l[i] >> y[i];
    }
    vector<int> valsT;
    {
        for (int i = 1; i <= n; ++i) {
            valsT.push_back(a[i]);
            valsT.push_back(b[i]);
        }
        for (int i = 1; i <= q; ++i) {
            valsT.push_back(y[i]);
        }
        sort(valsT.begin(), valsT.end());
        valsT.resize(unique(valsT.begin(), valsT.end()) - valsT.begin());
        revT.resize(valsT.size() + 1);
        for (int i = 0; i < valsT.size(); ++i) idT[valsT[i]] = i + 1, revT[i + 1] = valsT[i];
        for (int i = 1; i <= n; ++i) a[i] = idT[a[i]], b[i] = idT[b[i]];
        for (int i = 1; i <= q; ++i) y[i] = idT[y[i]];
    }
    vector<int> valsX;
    {
        for (int i = 1; i <= n; ++i) {
            valsX.push_back(x[i]);
        }
        for (int i = 1; i <= q; ++i) {
            valsX.push_back(l[i]);
        }
        sort(valsX.begin(), valsX.end());
        valsX.resize(unique(valsX.begin(), valsX.end()) - valsX.begin());
        revX.resize(valsX.size() + 1);
        for (int i = 0; i < valsX.size(); ++i) idX[valsX[i]] = i + 1, revX[i + 1] = valsX[i];
        for (int i = 1; i <= n; ++i) x[i] = idX[x[i]];
        for (int i = 1; i <= q; ++i) l[i] = idX[l[i]];
    }
    szX = valsX.size();
    tmin.init(szX);
    tmax.init(szX);
    vector<vector<int>> occ(k + 1);
    for (int i = 1; i <= n; ++i) {
        occ[t[i]].push_back(x[i]);
    }
    for (int i = 1; i <= k; ++i) {
        if (occ[i].empty()) {
            for (int j = 1; j <= q; j++) cout << -1 << "\n";
            return 0;
        }
        sort(occ[i].begin(), occ[i].end());
        int x = occ[i][0];
        tmax.ckmax(1, x, revX[x]);
        for (int j = 1; j < occ[i].size(); ++j) {
            int p1 = occ[i][j - 1];
            int p2 = occ[i][j];
            int mid = get_split(p1, p2);
            tmin.ckmin(p1, mid, revX[p1]);
            tmax.ckmax(mid + 1, p2, revX[p2]);
        }
        int y = occ[i].back();
        tmin.ckmin(y, valsX.size(), revX[y]);
    }
    for (int i = 1; i <= q; ++i) {
        add_queries(1, 1, valsT.size(), y[i], l[i], i);
    }
    for (int i = 1; i <= n; ++i) {
        add_rem(1, 1, valsT.size(), 1, a[i] - 1, x[i], t[i]);
        add_rem(1, 1, valsT.size(), b[i] + 1, valsT.size(), x[i], t[i]);
    }
    for (int i = 1; i <= n; ++i) {
        s[t[i]].insert(x[i]);
        ++f[t[i]];
    }
    cnt = k;
    solve(1, 1, valsT.size());
    for (int i = 1; i <= q; ++i) {
        cout << sol[i] << "\n";
    }
    return 0;
}

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