Submission #160950

#	Time	Username	Problem	Language	Result	Execution time	Memory
160950		Minnakhmetov	New Home (APIO18_new_home)	C++14	47 / 100	5045 ms	273016 KiB

new_home

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

struct E {
    int p, t, x, y;
};

const int N = 3e5 + 5, INF = 1e9, MAX = 1e8;
int n, q, k, cc, cq;
int ans[N], loc[N], num[N];

vector<int> vx;
multiset<int> occ[N];
map<pair<int, int>, vector<int>> mp;
vector<pair<int, int>> t[N * 4];
pair<int, int> his[N * 20];
int len = 0;

struct ST {
    int t[N];

    ST() {
        fill(t, t + N, -INF);
    }

    void upd(int x, int y) {
        for (; x < N; x |= x + 1) {
            his[len++] = {x, t[x]};
            t[x] = max(t[x], y);
        }
    }

    int que(int x) {
        int ans = -INF;
        for (; x >= 0; x = (x & (x + 1)) - 1)
            ans = max(ans, t[x]);
        return ans;
    }
} fent;

void upd(int l, int r, pair<int, int> p, int v, int L, int R) {
    if (l > r)
        return;
    if (L == l && R == r) {
        t[v].push_back(p);
    }
    else {
        int m = (L + R) >> 1;
        upd(l, min(m, r), p, v * 2, L, m);
        upd(max(m + 1, l), r, p, v * 2 + 1, m + 1, R);
    }
}

void startSeg(int x, int y) {
    mp[{x, y}].push_back(cq);
}

void endSeg(int x, int y) {
    // cout << "!" << x << " " << y << "\n";
    auto p = make_pair(x, y);
    upd(mp[{x, y}].back(), cq - 1, p, 1, 0, q - 1);
    // cout << "SEG_END " << mp[{x, y}].back() << " " << cq - 1 << " " << x << " " << y << "\n";
    mp[{x, y}].pop_back();
}

void updBeg(int x, bool add) {
    // cout << "BEG " << x << " " << add << "\n";
    if (add)
        startSeg(0, x);
    else
        endSeg(0, x);
}

void updBetween(int x, int y, bool add) {
    // cout << "BET " << x << " " << y << " " << add << "\n";
    if (x == y)
        return;
    int m = (x + y) / 2;
    if ((x + y) % 2)
        m++;

    int m1 = lower_bound(all(vx), m) - vx.begin();
    if (add)
        startSeg(m1, y);
    else
        endSeg(m1, y);
}

void calcAns(int v, int L, int R) {
    int tmp = len;

    for (auto &p : t[v]) {
        fent.upd(p.first, p.second);
    }

    if (L == R) {
        ans[num[L]] = max(ans[num[L]], fent.que(loc[L]) - vx[loc[L]]);
    }
    else {
        int m = (L + R) >> 1;
        calcAns(v * 2, L, m);
        calcAns(v * 2 + 1, m + 1, R);
    }

    while (len > tmp) {
        len--;
        fent.t[his[len].first] = his[len].second;
    }
}

void solve(vector<E> evs) {
    vx.clear();
    mp.clear();
    for (int i = 0; i < N; i++) {
        occ[i].clear();
    }

    for (int i = 0; i < N * 4; i++) {
        t[i].clear();
    }

    for (E e : evs) {
        if (e.t == 2)
            vx.push_back(e.x);
    }

    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());

    cc = vx.size();
    cq = 0;

    for (E e : evs) {
        // cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
        if (e.t == 0) {
            auto it = occ[e.y].upper_bound(e.x);
            if (!occ[e.y].empty()) {
                if (it != occ[e.y].begin() && it != occ[e.y].end()) {
                    updBetween(*prev(it), *it, false);
                }
                if (it == occ[e.y].begin()) {
                    updBeg(*it, false);
                }
            }

            it = occ[e.y].insert(e.x);

            if (it == occ[e.y].begin()) 
                updBeg(*it, true);
            else
                updBetween(*prev(it), *it, true);

            if (next(it) != occ[e.y].end())
                updBetween(*it, *next(it), true);

        }
        else if (e.t == 1) {
            auto it = occ[e.y].find(e.x);

            if (it == occ[e.y].begin()) 
                updBeg(*it, false);
            else
                updBetween(*prev(it), *it, false);

            if (next(it) != occ[e.y].end())
                updBetween(*it, *next(it), false);

            if (it != occ[e.y].begin() && next(it) != occ[e.y].end())
                updBetween(*prev(it), *next(it), true);
            if (it == occ[e.y].begin() && occ[e.y].size() > 1)
                updBeg(*next(it), true);

            occ[e.y].erase(it);
        }
        else {
            loc[cq] = lower_bound(all(vx), e.x) - vx.begin();
            num[cq] = e.y;
            cq++;
        }
    }

    calcAns(1, 0, q - 1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> k >> q;

    vector<E> evs;

    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        t--;
        evs.push_back({a, 0, x, t});
        evs.push_back({b + 1, 1, x, t});
        vx.push_back(x);
    }

    for (int i = 0; i < k; i++) {
        evs.push_back({1, 0, INF, i});
        evs.push_back({MAX, 1, INF, i});
    }

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        evs.push_back({y, 2, x, i});
    }

    sort(all(evs), [](const E &a, const E &b) {
        return a.p == b.p ? a.t < b.t : a.p < b.p;
    });

    solve(evs);
    for (E &e : evs)
        e.x = INF - e.x;
    solve(evs);

    for (int i = 0; i < q; i++) {
        if (ans[i] < INF / 2) {
            cout << ans[i] << "\n";
        }
        else {
            cout << "-1\n";
        }
    }

    return 0;
}

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