oj.uz

Submission #161016

# Submission time Handle Problem Language Result Execution time Memory
161016 2019-10-31T08:14:50 Z Minnakhmetov New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 382352 KB 
#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;
};
 
struct U {
    int l, r;
    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];
unordered_map<int, vector<int>> mp[2][N];
 
vector<int> vx;
multiset<int> occ[N];
vector<pair<int, int>> t[N * 4];
vector<U> updates[2];
 
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 type, int x, int y) {
    mp[type][x][y].push_back(cq);
}
 
void endSeg(int type, int x, int y) {
    updates[type].push_back({mp[type][x][y].back(), cq - 1, {x, y}});
    mp[type][x][y].pop_back();
}
 
void updBeg(int x, bool add) {
    if (add)
        startSeg(0, 0, x);
    else
        endSeg(0, 0, x);
}
 
void updBetween(int x, int y, bool add) {
    if (x == y)
        return;
    int m = (x + y) / 2;
    if ((x + y) % 2)
        m++;

    // cout << "BET " << x << " " << y << " " << add << "\n";
 
    int m1 = lower_bound(all(vx), m) - vx.begin();
    if (add) {
        startSeg(0, m1, y);
        startSeg(1, cc - m1, INF - x);
    }
    else {
        endSeg(0, m1, y);
        endSeg(1, cc - m1, INF - x);
    }
}

void updEnd(int x, bool add) {
    if (add)
        startSeg(1, 0, INF - x);
    else
        endSeg(1, 0, INF - x);
}
 
void calcAns(int v, int L, int R) {
    if (L != R) {
        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];
    }
 
    int i = 0, mx = -INF;
    for (int j = L; j <= R; j++) {
        while (i < t[v].size() && t[v][i].first <= lt[j].first) {
            mx = max(mx, t[v][i].second);
            i++;
        }
        ans[lt[j].second] = max(ans[lt[j].second], mx - vx[lt[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;
 
    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);
                }
                if (it == occ[e.y].end()) {
                    updEnd(*prev(it), false);
                }
            }
 
            it = occ[e.y].insert(e.x);
 
            if (it == occ[e.y].begin()) 
                updBeg(e.x, true);
            else
                updBetween(*prev(it), e.x, true);
 
            if (next(it) != occ[e.y].end())
                updBetween(e.x, *next(it), true);
            else
                updEnd(e.x, 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);
            else
                updEnd(e.x, 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);

            if (next(it) == occ[e.y].end() &&
                occ[e.y].size() > 1)
                updEnd(*prev(it), true);
 
            occ[e.y].erase(it);
        }
        else {
            cq++;
        }
    }

    for (int i = 0; i < 2; i++) {
        sort(all(updates[i]), [](const U &a, const U &b) {
            return a.p.first < b.p.first;
        });
    }
}

void solve(vector<U> updates, vector<E> evs) {
    for (int i = 0; i < N * 4; i++)
        t[i].clear();

    cq = 0;

    for (E &e : evs) {
        if (e.t == 2) {
            lt[cq++] = {lower_bound(all(vx), e.x) - vx.begin(), e.y};
        }
    }

    for (U u : updates) {
        // cout << u.l << " " << u.r << " " << u.p.first << " " << u.p.second << "\n";
        upd(u.l, u.r, u.p, 1, 0, q - 1);
    }

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

    calcUpdates(evs);
    solve(updates[0], evs);

    for (E &e : evs)
        e.x = INF - e.x;
    for (int &x : vx)
        x = INF - x;
    reverse(all(vx));

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

Compilation message

new_home.cpp: In function 'void calcAns(int, int, int)':
new_home.cpp:104:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < t[v].size() && t[v][i].first <= lt[j].first) {
                ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 75512 KB Output is correct
2 Correct 81 ms 75512 KB Output is correct
3 Correct 80 ms 75512 KB Output is correct
4 Correct 82 ms 75652 KB Output is correct
5 Correct 96 ms 75612 KB Output is correct
6 Correct 86 ms 75936 KB Output is correct
7 Correct 85 ms 75748 KB Output is correct
8 Correct 86 ms 75896 KB Output is correct
9 Correct 84 ms 75896 KB Output is correct
10 Correct 93 ms 75948 KB Output is correct
11 Correct 83 ms 75768 KB Output is correct
12 Correct 83 ms 75768 KB Output is correct
13 Correct 84 ms 75712 KB Output is correct
14 Correct 98 ms 75836 KB Output is correct
15 Correct 86 ms 75896 KB Output is correct
16 Correct 86 ms 75868 KB Output is correct
17 Correct 85 ms 76024 KB Output is correct
18 Correct 84 ms 75896 KB Output is correct
19 Correct 88 ms 75896 KB Output is correct
20 Correct 88 ms 75900 KB Output is correct
21 Correct 83 ms 75772 KB Output is correct
22 Correct 83 ms 75896 KB Output is correct
23 Correct 86 ms 75900 KB Output is correct
24 Correct 85 ms 75912 KB Output is correct
25 Correct 85 ms 75896 KB Output is correct
26 Correct 84 ms 75896 KB Output is correct
27 Correct 84 ms 75768 KB Output is correct
28 Correct 87 ms 75948 KB Output is correct
29 Correct 84 ms 75768 KB Output is correct
30 Correct 83 ms 75640 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 75512 KB Output is correct
2 Correct 81 ms 75512 KB Output is correct
3 Correct 80 ms 75512 KB Output is correct
4 Correct 82 ms 75652 KB Output is correct
5 Correct 96 ms 75612 KB Output is correct
6 Correct 86 ms 75936 KB Output is correct
7 Correct 85 ms 75748 KB Output is correct
8 Correct 86 ms 75896 KB Output is correct
9 Correct 84 ms 75896 KB Output is correct
10 Correct 93 ms 75948 KB Output is correct
11 Correct 83 ms 75768 KB Output is correct
12 Correct 83 ms 75768 KB Output is correct
13 Correct 84 ms 75712 KB Output is correct
14 Correct 98 ms 75836 KB Output is correct
15 Correct 86 ms 75896 KB Output is correct
16 Correct 86 ms 75868 KB Output is correct
17 Correct 85 ms 76024 KB Output is correct
18 Correct 84 ms 75896 KB Output is correct
19 Correct 88 ms 75896 KB Output is correct
20 Correct 88 ms 75900 KB Output is correct
21 Correct 83 ms 75772 KB Output is correct
22 Correct 83 ms 75896 KB Output is correct
23 Correct 86 ms 75900 KB Output is correct
24 Correct 85 ms 75912 KB Output is correct
25 Correct 85 ms 75896 KB Output is correct
26 Correct 84 ms 75896 KB Output is correct
27 Correct 84 ms 75768 KB Output is correct
28 Correct 87 ms 75948 KB Output is correct
29 Correct 84 ms 75768 KB Output is correct
30 Correct 83 ms 75640 KB Output is correct
31 Correct 1342 ms 147528 KB Output is correct
32 Correct 251 ms 90592 KB Output is correct
33 Correct 1370 ms 145556 KB Output is correct
34 Correct 1235 ms 145876 KB Output is correct
35 Correct 1399 ms 147912 KB Output is correct
36 Correct 1289 ms 146724 KB Output is correct
37 Correct 920 ms 141776 KB Output is correct
38 Correct 892 ms 138828 KB Output is correct
39 Correct 665 ms 132984 KB Output is correct
40 Correct 701 ms 133592 KB Output is correct
41 Correct 947 ms 128696 KB Output is correct
42 Correct 912 ms 128904 KB Output is correct
43 Correct 207 ms 90904 KB Output is correct
44 Correct 942 ms 127968 KB Output is correct
45 Correct 815 ms 125756 KB Output is correct
46 Correct 748 ms 121384 KB Output is correct
47 Correct 533 ms 117036 KB Output is correct
48 Correct 500 ms 116548 KB Output is correct
49 Correct 615 ms 121392 KB Output is correct
50 Correct 668 ms 125920 KB Output is correct
51 Correct 623 ms 120404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3857 ms 285280 KB Output is correct
2 Correct 4345 ms 306248 KB Output is correct
3 Correct 2539 ms 337168 KB Output is correct
4 Correct 3368 ms 283168 KB Output is correct
5 Correct 4142 ms 291536 KB Output is correct
6 Correct 4303 ms 316792 KB Output is correct
7 Correct 2545 ms 334332 KB Output is correct
8 Correct 3170 ms 292904 KB Output is correct
9 Correct 3743 ms 298388 KB Output is correct
10 Correct 4014 ms 331860 KB Output is correct
11 Correct 2665 ms 321800 KB Output is correct
12 Correct 3556 ms 327496 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5117 ms 382352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 75512 KB Output is correct
2 Correct 81 ms 75512 KB Output is correct
3 Correct 80 ms 75512 KB Output is correct
4 Correct 82 ms 75652 KB Output is correct
5 Correct 96 ms 75612 KB Output is correct
6 Correct 86 ms 75936 KB Output is correct
7 Correct 85 ms 75748 KB Output is correct
8 Correct 86 ms 75896 KB Output is correct
9 Correct 84 ms 75896 KB Output is correct
10 Correct 93 ms 75948 KB Output is correct
11 Correct 83 ms 75768 KB Output is correct
12 Correct 83 ms 75768 KB Output is correct
13 Correct 84 ms 75712 KB Output is correct
14 Correct 98 ms 75836 KB Output is correct
15 Correct 86 ms 75896 KB Output is correct
16 Correct 86 ms 75868 KB Output is correct
17 Correct 85 ms 76024 KB Output is correct
18 Correct 84 ms 75896 KB Output is correct
19 Correct 88 ms 75896 KB Output is correct
20 Correct 88 ms 75900 KB Output is correct
21 Correct 83 ms 75772 KB Output is correct
22 Correct 83 ms 75896 KB Output is correct
23 Correct 86 ms 75900 KB Output is correct
24 Correct 85 ms 75912 KB Output is correct
25 Correct 85 ms 75896 KB Output is correct
26 Correct 84 ms 75896 KB Output is correct
27 Correct 84 ms 75768 KB Output is correct
28 Correct 87 ms 75948 KB Output is correct
29 Correct 84 ms 75768 KB Output is correct
30 Correct 83 ms 75640 KB Output is correct
31 Correct 1342 ms 147528 KB Output is correct
32 Correct 251 ms 90592 KB Output is correct
33 Correct 1370 ms 145556 KB Output is correct
34 Correct 1235 ms 145876 KB Output is correct
35 Correct 1399 ms 147912 KB Output is correct
36 Correct 1289 ms 146724 KB Output is correct
37 Correct 920 ms 141776 KB Output is correct
38 Correct 892 ms 138828 KB Output is correct
39 Correct 665 ms 132984 KB Output is correct
40 Correct 701 ms 133592 KB Output is correct
41 Correct 947 ms 128696 KB Output is correct
42 Correct 912 ms 128904 KB Output is correct
43 Correct 207 ms 90904 KB Output is correct
44 Correct 942 ms 127968 KB Output is correct
45 Correct 815 ms 125756 KB Output is correct
46 Correct 748 ms 121384 KB Output is correct
47 Correct 533 ms 117036 KB Output is correct
48 Correct 500 ms 116548 KB Output is correct
49 Correct 615 ms 121392 KB Output is correct
50 Correct 668 ms 125920 KB Output is correct
51 Correct 623 ms 120404 KB Output is correct
52 Correct 707 ms 140372 KB Output is correct
53 Correct 680 ms 128280 KB Output is correct
54 Correct 992 ms 138268 KB Output is correct
55 Correct 801 ms 136272 KB Output is correct
56 Correct 769 ms 137112 KB Output is correct
57 Correct 838 ms 131668 KB Output is correct
58 Correct 822 ms 135244 KB Output is correct
59 Correct 790 ms 136680 KB Output is correct
60 Correct 839 ms 131992 KB Output is correct
61 Correct 266 ms 109308 KB Output is correct
62 Correct 674 ms 142204 KB Output is correct
63 Correct 866 ms 138196 KB Output is correct
64 Correct 925 ms 138076 KB Output is correct
65 Correct 992 ms 136844 KB Output is correct
66 Correct 892 ms 132696 KB Output is correct
67 Correct 327 ms 102032 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 75512 KB Output is correct
2 Correct 81 ms 75512 KB Output is correct
3 Correct 80 ms 75512 KB Output is correct
4 Correct 82 ms 75652 KB Output is correct
5 Correct 96 ms 75612 KB Output is correct
6 Correct 86 ms 75936 KB Output is correct
7 Correct 85 ms 75748 KB Output is correct
8 Correct 86 ms 75896 KB Output is correct
9 Correct 84 ms 75896 KB Output is correct
10 Correct 93 ms 75948 KB Output is correct
11 Correct 83 ms 75768 KB Output is correct
12 Correct 83 ms 75768 KB Output is correct
13 Correct 84 ms 75712 KB Output is correct
14 Correct 98 ms 75836 KB Output is correct
15 Correct 86 ms 75896 KB Output is correct
16 Correct 86 ms 75868 KB Output is correct
17 Correct 85 ms 76024 KB Output is correct
18 Correct 84 ms 75896 KB Output is correct
19 Correct 88 ms 75896 KB Output is correct
20 Correct 88 ms 75900 KB Output is correct
21 Correct 83 ms 75772 KB Output is correct
22 Correct 83 ms 75896 KB Output is correct
23 Correct 86 ms 75900 KB Output is correct
24 Correct 85 ms 75912 KB Output is correct
25 Correct 85 ms 75896 KB Output is correct
26 Correct 84 ms 75896 KB Output is correct
27 Correct 84 ms 75768 KB Output is correct
28 Correct 87 ms 75948 KB Output is correct
29 Correct 84 ms 75768 KB Output is correct
30 Correct 83 ms 75640 KB Output is correct
31 Correct 1342 ms 147528 KB Output is correct
32 Correct 251 ms 90592 KB Output is correct
33 Correct 1370 ms 145556 KB Output is correct
34 Correct 1235 ms 145876 KB Output is correct
35 Correct 1399 ms 147912 KB Output is correct
36 Correct 1289 ms 146724 KB Output is correct
37 Correct 920 ms 141776 KB Output is correct
38 Correct 892 ms 138828 KB Output is correct
39 Correct 665 ms 132984 KB Output is correct
40 Correct 701 ms 133592 KB Output is correct
41 Correct 947 ms 128696 KB Output is correct
42 Correct 912 ms 128904 KB Output is correct
43 Correct 207 ms 90904 KB Output is correct
44 Correct 942 ms 127968 KB Output is correct
45 Correct 815 ms 125756 KB Output is correct
46 Correct 748 ms 121384 KB Output is correct
47 Correct 533 ms 117036 KB Output is correct
48 Correct 500 ms 116548 KB Output is correct
49 Correct 615 ms 121392 KB Output is correct
50 Correct 668 ms 125920 KB Output is correct
51 Correct 623 ms 120404 KB Output is correct
52 Correct 3857 ms 285280 KB Output is correct
53 Correct 4345 ms 306248 KB Output is correct
54 Correct 2539 ms 337168 KB Output is correct
55 Correct 3368 ms 283168 KB Output is correct
56 Correct 4142 ms 291536 KB Output is correct
57 Correct 4303 ms 316792 KB Output is correct
58 Correct 2545 ms 334332 KB Output is correct
59 Correct 3170 ms 292904 KB Output is correct
60 Correct 3743 ms 298388 KB Output is correct
61 Correct 4014 ms 331860 KB Output is correct
62 Correct 2665 ms 321800 KB Output is correct
63 Correct 3556 ms 327496 KB Output is correct
64 Execution timed out 5117 ms 382352 KB Time limit exceeded
65 Halted 0 ms 0 KB -