Submission #161054

#	Time	Username	Problem	Language	Result	Execution time	Memory
161054		Minnakhmetov	New Home (APIO18_new_home)	C++14	100 / 100	4786 ms	378772 KiB

new_home

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

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
 
struct E {
    int p, t, x, y;
};
 
struct U {
    int l, r;
    pair<int, pair<int, int>> p;
};
 
const int N = 3e5 + 5, INF = 1e9, MAX = 1e8;
int n, q, k, cq, cc;
int ans[N];
pair<int, int> lt[N], tmp[N];
map<pair<int, int>, pair<int, int>> mp[N];
bool ok[N];
 
vector<int> vx;
multiset<int> occ[N];
vector<pair<int, pair<int, int>>> t[N * 4];
vector<U> updates;
 
void upd(int l, int r, pair<int, 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, pair<int, int> y) {
    auto &p = mp[x][y];
    if (p.first == 0)
        p.second = cq;
    p.first++;
}
 
void endSeg(int x, pair<int, int> y) {
    auto &p = mp[x][y];
    if (p.first == 1)
        updates.push_back({p.second, cq - 1, {x, y}});
    p.first--;    
}
 
void updBetween(int x, int y, bool add) {
    if (x == y || x == -INF && y == INF)
        return;

    int m1 = lower_bound(all(vx), (x + y + 1) >> 1) - vx.begin();
 
    if (add)
        startSeg(m1, {y, -x});
    else
        endSeg(m1, {y, -x});
}
 
void calcAns(int v, int L, int R) {
    if (L == R) {
        tmp[0] = lt[L];
    }
    else {
        int m = (L + R) >> 1;
        calcAns(v * 2, L, m);
        calcAns(v * 2 + 1, m + 1, R);
        
        int x = L, y = m + 1, z = 0;
        while (x <= m || y <= R) {
            if (x <= m && (y == R + 1 || lt[x].first < lt[y].first))
                tmp[z] = lt[x++];
            else 
                tmp[z] = lt[y++];
            z++;
        }
        for (int i = L; i <= R; i++)
            lt[i] = tmp[i - L];
    }

    if (!t[v].empty()) {
        int i = 0, mx = -INF;
        for (int j = 0; j <= R - L; j++) {
            while (i < t[v].size() && t[v][i].first <= tmp[j].first) {
                mx = max(mx, t[v][i].second.first);
                i++;
            }
            ans[tmp[j].second] = max(ans[tmp[j].second], mx - vx[tmp[j].first]);
        }    

        i = t[v].size() - 1, mx = -INF;
        for (int j = R - L; j >= 0; j--) {
            while (i >= 0 && t[v][i].first > tmp[j].first) {
                mx = max(mx, t[v][i].second.second);
                i--;
            }
            ans[tmp[j].second] = max(ans[tmp[j].second], mx + vx[tmp[j].first]);
        }
    }
}
 
void calcUpdates(vector<E> &evs) { 
    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;
 
    int types_on = 0;
 
    for (E &e : evs) {
        // cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
        if (e.t == 0) {
            if (occ[e.y].size() == 2)
                types_on++;

            auto it = occ[e.y].insert(e.x);
 
            updBetween(*prev(it), *it, true);
            updBetween(*it, *next(it), true);
            updBetween(*prev(it), *next(it), false);
 
        }
        else if (e.t == 1) {
            auto it = occ[e.y].find(e.x);
 
            updBetween(*prev(it), *it, false);
            updBetween(*it, *next(it), false);
            updBetween(*prev(it), *next(it), true);
 
            occ[e.y].erase(it);
 
            if (occ[e.y].size() == 2)
                types_on--;
        }
        else {
            ok[e.y] = (types_on == k);
            lt[cq++] = {lower_bound(all(vx), e.x) - vx.begin(), e.y};
        }
    }
 
    sort(all(updates), [](const U &a, const U &b) {
        return a.p.first < b.p.first;
    });
}
 
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});
    }
 
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        evs.push_back({y, 2, x, i});
    }
 
    for (int i = 0; i < k; i++) {
        occ[i].insert(-INF);
        occ[i].insert(INF);
    }
 
    sort(all(evs), [](const E &a, const E &b) {
        return a.p == b.p ? a.t < b.t : a.p < b.p;
    });
 
    calcUpdates(evs);
 
    for (U &u : updates) {
        upd(u.l, u.r, u.p, 1, 0, q - 1);
    }
 
    calcAns(1, 0, q - 1);
 
    for (int i = 0; i < q; i++) {
        if (ok[i]) {
            cout << ans[i] << "\n";
        }
        else {
            cout << "-1\n";
        }
    }
 
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void updBetween(int, int, bool)':
new_home.cpp:60:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (x == y || x == -INF && y == INF)
                   ~~~~~~~~~~^~~~~~~~~~~
new_home.cpp: In function 'void calcAns(int, int, int)':
new_home.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (i < t[v].size() && t[v][i].first <= tmp[j].first) {
                    ~~^~~~~~~~~~~~~

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