Submission #1259183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259183		antonn	New Home (APIO18_new_home)	C++20	80 / 100	5109 ms	516368 KiB

new_home

#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;
}

// o sa trb sa modifici putin ainturile astea
// gen sa adaugi si undo

struct STMin { // min=, min query
    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) {
        //cout << "MIN " << l << " " << r << " " << x << "\n";
        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 { // max=, max query
    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) {
        //cout << "AJUNS IN " << v << " [" << tl << ", " << tr << "] \n";
        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) {
        //cout << "MAX " << l << " " << r << " " << x << "\n";
        if (l > r) return;
        //cout << "CKMAX " << l << " " << r << " " << x << "\n";
        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) {
    //cout << "AM INTRAT IN " << v << ": ";
    //for (int i = 0; i < tmin.t.size(); ++i) cout << tmin.t[i] << " ";
    //cout << "\n";
    int time_min = tmin.Time;
    int time_max = tmax.Time;
    tmin.Time++;
    tmax.Time++;
    for (auto [x, t] : updates[v]) {
        // scoate l pe (x, t)
        //cout << "SCOT " << revX[x] << " " << t << "\n";
        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 {
                //cout << "DA\n";
                //cout << "max= " << 1 << " " << (*next(it)) << " " << revX[*next(it)] << "\n";
                tmax.ckmax(1, *next(it), revX[*next(it)]);
            }
            //cout << "DA\n";
        } 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 {
                //cout << "! " << id << ": " << revX[x] << "\n";
                //for (int i = 1; i <= k; ++i) {
                    //cout << i << ": ";
                    //for (auto f : s[i]) cout << revX[f] << " ";
                    //cout << "\n";
                //}
                //cout << "? " << tmin.get(x) << "\n";
                //cout << "? " << tmax.get(x) << "\n";
                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]) {
        // baga l pe (x, t)
        //cout << "BAG " << revX[x] << " " << t << "\n";
        f[t]++;
        if (f[t] == 1) cnt++;
        s[t].insert(x);
    }
    //cout << "AM IESIT DIN " << v << ": ";
    //for (int i = 0; i < tmin.t.size(); ++i) cout << tmin.t[i] << " ";
    //cout << "\n";
}

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];
    }
    // normalizam timpul
    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]];
    }
    // normalizam locatile
    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]];
    }
    //cout << "!!! VALSX ";
    //for (int i = 0; i < valsX.size(); ++i) cout << valsX[i] << " ";
    //cout << "\n";
    szX = valsX.size();
    tmin.init(szX);
    tmax.init(szX);
    //tmax.ckmax(1, 2, 3);
    //tmax.ckmax(3, 3, 4);
    //tmax.ckmax(1, 5, 7);
    //tmax.ckmax(6, 6, 9);
    //tmax.ckmax(1, 6, 9);
    //cout << "HERE " << tmax.get(4) << "\n";
    //return 0;
    // rezolvam problema daca a[i] = 1 si b[i] = 1e8 pentru orice i
    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);
            //cout << "! " << p1 << " " << p2 << " " << mid << "\n";
            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]);
    }
    // aint pe timp
    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;
}
/*
2 1 1
4 1 31 77
9 1 9 93
8 14

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

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