oj.uz

Submission #161044

# Submission time Handle Problem Language Result Execution time Memory
161044 2019-10-31T10:15:27 Z Minnakhmetov New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 389240 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, 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>, vector<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);
    }
}
 
bool dummy(int y) {
    return abs(y) == INF || abs(INF - y) == INF;
}
 
void startSeg(int x, pair<int, int> y) {
    if (dummy(y.first) && dummy(y.second))
        return;
    mp[x][y].push_back(cq);
}
 
void endSeg(int x, pair<int, int> y) {
    if (dummy(y.first) && dummy(y.second))
        return;
    auto &v = mp[x][y];
    if (v.size() == 1)
        updates.push_back({v.back(), cq - 1, {x, y}});
    v.pop_back();
}
 
void updBetween(int x, int y, bool add) {
    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, INF - x});
    else
        endSeg(m1, {y, INF - 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];
    }
 
    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]);
    }    
 
    reverse(tmp, tmp + R - L + 1);
 
    for (int j = 0; j <= R - L; j++)
        tmp[j].first = cc - 1 - tmp[j].first;
 
    // for (auto p : t[v]) {
    //     cout << p.first << " " << p.second.second << "\n";
    // }
    // for (auto p : t[v]) {
    //     cout << p.first << " " << p.second << "\n";
    // }
 
    reverse(all(t[v]));
    for (auto &p : t[v]) {
        p.first = cc - p.first;
    }
 
    
 
 
    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.second);
            i++;
        }
        ans[tmp[j].second] = max(ans[tmp[j].second], mx - INF + vx[cc - 1 - 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

new_home.cpp: In function 'void calcAns(int, int, int)':
new_home.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < t[v].size() && t[v][i].first <= tmp[j].first) {
                ~~^~~~~~~~~~~~~
new_home.cpp:128:18: 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 56696 KB Output is correct
2 Correct 59 ms 56700 KB Output is correct
3 Correct 60 ms 56696 KB Output is correct
4 Correct 60 ms 56824 KB Output is correct
5 Correct 60 ms 56828 KB Output is correct
6 Correct 61 ms 56956 KB Output is correct
7 Correct 60 ms 56952 KB Output is correct
8 Correct 62 ms 57080 KB Output is correct
9 Correct 61 ms 57080 KB Output is correct
10 Correct 61 ms 57096 KB Output is correct
11 Correct 60 ms 56952 KB Output is correct
12 Correct 61 ms 57004 KB Output is correct
13 Correct 60 ms 56952 KB Output is correct
14 Correct 63 ms 57020 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 63 ms 57080 KB Output is correct
17 Correct 63 ms 57080 KB Output is correct
18 Correct 65 ms 57028 KB Output is correct
19 Correct 64 ms 57112 KB Output is correct
20 Correct 62 ms 57084 KB Output is correct
21 Correct 61 ms 56824 KB Output is correct
22 Correct 62 ms 57056 KB Output is correct
23 Correct 61 ms 57208 KB Output is correct
24 Correct 59 ms 57080 KB Output is correct
25 Correct 56 ms 57048 KB Output is correct
26 Correct 56 ms 56932 KB Output is correct
27 Correct 55 ms 56952 KB Output is correct
28 Correct 54 ms 56952 KB Output is correct
29 Correct 54 ms 56952 KB Output is correct
30 Correct 54 ms 56824 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 56696 KB Output is correct
2 Correct 59 ms 56700 KB Output is correct
3 Correct 60 ms 56696 KB Output is correct
4 Correct 60 ms 56824 KB Output is correct
5 Correct 60 ms 56828 KB Output is correct
6 Correct 61 ms 56956 KB Output is correct
7 Correct 60 ms 56952 KB Output is correct
8 Correct 62 ms 57080 KB Output is correct
9 Correct 61 ms 57080 KB Output is correct
10 Correct 61 ms 57096 KB Output is correct
11 Correct 60 ms 56952 KB Output is correct
12 Correct 61 ms 57004 KB Output is correct
13 Correct 60 ms 56952 KB Output is correct
14 Correct 63 ms 57020 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 63 ms 57080 KB Output is correct
17 Correct 63 ms 57080 KB Output is correct
18 Correct 65 ms 57028 KB Output is correct
19 Correct 64 ms 57112 KB Output is correct
20 Correct 62 ms 57084 KB Output is correct
21 Correct 61 ms 56824 KB Output is correct
22 Correct 62 ms 57056 KB Output is correct
23 Correct 61 ms 57208 KB Output is correct
24 Correct 59 ms 57080 KB Output is correct
25 Correct 56 ms 57048 KB Output is correct
26 Correct 56 ms 56932 KB Output is correct
27 Correct 55 ms 56952 KB Output is correct
28 Correct 54 ms 56952 KB Output is correct
29 Correct 54 ms 56952 KB Output is correct
30 Correct 54 ms 56824 KB Output is correct
31 Correct 902 ms 120080 KB Output is correct
32 Correct 171 ms 62688 KB Output is correct
33 Correct 794 ms 117152 KB Output is correct
34 Correct 784 ms 117460 KB Output is correct
35 Correct 942 ms 120052 KB Output is correct
36 Correct 852 ms 119896 KB Output is correct
37 Correct 607 ms 111084 KB Output is correct
38 Correct 571 ms 110760 KB Output is correct
39 Correct 449 ms 101204 KB Output is correct
40 Correct 495 ms 103472 KB Output is correct
41 Correct 747 ms 109332 KB Output is correct
42 Correct 728 ms 109816 KB Output is correct
43 Correct 155 ms 64864 KB Output is correct
44 Correct 751 ms 108564 KB Output is correct
45 Correct 662 ms 103384 KB Output is correct
46 Correct 545 ms 94280 KB Output is correct
47 Correct 395 ms 91396 KB Output is correct
48 Correct 360 ms 89732 KB Output is correct
49 Correct 440 ms 96444 KB Output is correct
50 Correct 530 ms 105980 KB Output is correct
51 Correct 439 ms 94076 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3111 ms 203276 KB Output is correct
2 Correct 3141 ms 202428 KB Output is correct
3 Correct 2890 ms 222664 KB Output is correct
4 Correct 3210 ms 206724 KB Output is correct
5 Correct 2665 ms 201156 KB Output is correct
6 Correct 2972 ms 204676 KB Output is correct
7 Correct 2429 ms 223512 KB Output is correct
8 Correct 2471 ms 209444 KB Output is correct
9 Correct 2376 ms 206796 KB Output is correct
10 Correct 2441 ms 209588 KB Output is correct
11 Correct 1667 ms 205056 KB Output is correct
12 Correct 1761 ms 206920 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4389 ms 312896 KB Output is correct
2 Correct 737 ms 94132 KB Output is correct
3 Correct 4188 ms 313068 KB Output is correct
4 Correct 3260 ms 287592 KB Output is correct
5 Correct 4252 ms 308612 KB Output is correct
6 Correct 3947 ms 304124 KB Output is correct
7 Correct 4019 ms 313260 KB Output is correct
8 Correct 4495 ms 313856 KB Output is correct
9 Correct 3068 ms 287324 KB Output is correct
10 Correct 3746 ms 299720 KB Output is correct
11 Correct 4423 ms 311600 KB Output is correct
12 Correct 4038 ms 312512 KB Output is correct
13 Correct 2064 ms 260684 KB Output is correct
14 Correct 1989 ms 257428 KB Output is correct
15 Correct 2422 ms 275660 KB Output is correct
16 Correct 2716 ms 289876 KB Output is correct
17 Correct 2653 ms 283060 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 56696 KB Output is correct
2 Correct 59 ms 56700 KB Output is correct
3 Correct 60 ms 56696 KB Output is correct
4 Correct 60 ms 56824 KB Output is correct
5 Correct 60 ms 56828 KB Output is correct
6 Correct 61 ms 56956 KB Output is correct
7 Correct 60 ms 56952 KB Output is correct
8 Correct 62 ms 57080 KB Output is correct
9 Correct 61 ms 57080 KB Output is correct
10 Correct 61 ms 57096 KB Output is correct
11 Correct 60 ms 56952 KB Output is correct
12 Correct 61 ms 57004 KB Output is correct
13 Correct 60 ms 56952 KB Output is correct
14 Correct 63 ms 57020 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 63 ms 57080 KB Output is correct
17 Correct 63 ms 57080 KB Output is correct
18 Correct 65 ms 57028 KB Output is correct
19 Correct 64 ms 57112 KB Output is correct
20 Correct 62 ms 57084 KB Output is correct
21 Correct 61 ms 56824 KB Output is correct
22 Correct 62 ms 57056 KB Output is correct
23 Correct 61 ms 57208 KB Output is correct
24 Correct 59 ms 57080 KB Output is correct
25 Correct 56 ms 57048 KB Output is correct
26 Correct 56 ms 56932 KB Output is correct
27 Correct 55 ms 56952 KB Output is correct
28 Correct 54 ms 56952 KB Output is correct
29 Correct 54 ms 56952 KB Output is correct
30 Correct 54 ms 56824 KB Output is correct
31 Correct 902 ms 120080 KB Output is correct
32 Correct 171 ms 62688 KB Output is correct
33 Correct 794 ms 117152 KB Output is correct
34 Correct 784 ms 117460 KB Output is correct
35 Correct 942 ms 120052 KB Output is correct
36 Correct 852 ms 119896 KB Output is correct
37 Correct 607 ms 111084 KB Output is correct
38 Correct 571 ms 110760 KB Output is correct
39 Correct 449 ms 101204 KB Output is correct
40 Correct 495 ms 103472 KB Output is correct
41 Correct 747 ms 109332 KB Output is correct
42 Correct 728 ms 109816 KB Output is correct
43 Correct 155 ms 64864 KB Output is correct
44 Correct 751 ms 108564 KB Output is correct
45 Correct 662 ms 103384 KB Output is correct
46 Correct 545 ms 94280 KB Output is correct
47 Correct 395 ms 91396 KB Output is correct
48 Correct 360 ms 89732 KB Output is correct
49 Correct 440 ms 96444 KB Output is correct
50 Correct 530 ms 105980 KB Output is correct
51 Correct 439 ms 94076 KB Output is correct
52 Correct 653 ms 114048 KB Output is correct
53 Correct 650 ms 109808 KB Output is correct
54 Correct 825 ms 119828 KB Output is correct
55 Correct 669 ms 117076 KB Output is correct
56 Correct 666 ms 117876 KB Output is correct
57 Correct 803 ms 112872 KB Output is correct
58 Correct 699 ms 113772 KB Output is correct
59 Correct 683 ms 114828 KB Output is correct
60 Correct 691 ms 112640 KB Output is correct
61 Correct 161 ms 72360 KB Output is correct
62 Correct 639 ms 117084 KB Output is correct
63 Correct 895 ms 120520 KB Output is correct
64 Correct 841 ms 121524 KB Output is correct
65 Correct 855 ms 121112 KB Output is correct
66 Correct 729 ms 115252 KB Output is correct
67 Correct 209 ms 64380 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 56696 KB Output is correct
2 Correct 59 ms 56700 KB Output is correct
3 Correct 60 ms 56696 KB Output is correct
4 Correct 60 ms 56824 KB Output is correct
5 Correct 60 ms 56828 KB Output is correct
6 Correct 61 ms 56956 KB Output is correct
7 Correct 60 ms 56952 KB Output is correct
8 Correct 62 ms 57080 KB Output is correct
9 Correct 61 ms 57080 KB Output is correct
10 Correct 61 ms 57096 KB Output is correct
11 Correct 60 ms 56952 KB Output is correct
12 Correct 61 ms 57004 KB Output is correct
13 Correct 60 ms 56952 KB Output is correct
14 Correct 63 ms 57020 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 63 ms 57080 KB Output is correct
17 Correct 63 ms 57080 KB Output is correct
18 Correct 65 ms 57028 KB Output is correct
19 Correct 64 ms 57112 KB Output is correct
20 Correct 62 ms 57084 KB Output is correct
21 Correct 61 ms 56824 KB Output is correct
22 Correct 62 ms 57056 KB Output is correct
23 Correct 61 ms 57208 KB Output is correct
24 Correct 59 ms 57080 KB Output is correct
25 Correct 56 ms 57048 KB Output is correct
26 Correct 56 ms 56932 KB Output is correct
27 Correct 55 ms 56952 KB Output is correct
28 Correct 54 ms 56952 KB Output is correct
29 Correct 54 ms 56952 KB Output is correct
30 Correct 54 ms 56824 KB Output is correct
31 Correct 902 ms 120080 KB Output is correct
32 Correct 171 ms 62688 KB Output is correct
33 Correct 794 ms 117152 KB Output is correct
34 Correct 784 ms 117460 KB Output is correct
35 Correct 942 ms 120052 KB Output is correct
36 Correct 852 ms 119896 KB Output is correct
37 Correct 607 ms 111084 KB Output is correct
38 Correct 571 ms 110760 KB Output is correct
39 Correct 449 ms 101204 KB Output is correct
40 Correct 495 ms 103472 KB Output is correct
41 Correct 747 ms 109332 KB Output is correct
42 Correct 728 ms 109816 KB Output is correct
43 Correct 155 ms 64864 KB Output is correct
44 Correct 751 ms 108564 KB Output is correct
45 Correct 662 ms 103384 KB Output is correct
46 Correct 545 ms 94280 KB Output is correct
47 Correct 395 ms 91396 KB Output is correct
48 Correct 360 ms 89732 KB Output is correct
49 Correct 440 ms 96444 KB Output is correct
50 Correct 530 ms 105980 KB Output is correct
51 Correct 439 ms 94076 KB Output is correct
52 Correct 3111 ms 203276 KB Output is correct
53 Correct 3141 ms 202428 KB Output is correct
54 Correct 2890 ms 222664 KB Output is correct
55 Correct 3210 ms 206724 KB Output is correct
56 Correct 2665 ms 201156 KB Output is correct
57 Correct 2972 ms 204676 KB Output is correct
58 Correct 2429 ms 223512 KB Output is correct
59 Correct 2471 ms 209444 KB Output is correct
60 Correct 2376 ms 206796 KB Output is correct
61 Correct 2441 ms 209588 KB Output is correct
62 Correct 1667 ms 205056 KB Output is correct
63 Correct 1761 ms 206920 KB Output is correct
64 Correct 4389 ms 312896 KB Output is correct
65 Correct 737 ms 94132 KB Output is correct
66 Correct 4188 ms 313068 KB Output is correct
67 Correct 3260 ms 287592 KB Output is correct
68 Correct 4252 ms 308612 KB Output is correct
69 Correct 3947 ms 304124 KB Output is correct
70 Correct 4019 ms 313260 KB Output is correct
71 Correct 4495 ms 313856 KB Output is correct
72 Correct 3068 ms 287324 KB Output is correct
73 Correct 3746 ms 299720 KB Output is correct
74 Correct 4423 ms 311600 KB Output is correct
75 Correct 4038 ms 312512 KB Output is correct
76 Correct 2064 ms 260684 KB Output is correct
77 Correct 1989 ms 257428 KB Output is correct
78 Correct 2422 ms 275660 KB Output is correct
79 Correct 2716 ms 289876 KB Output is correct
80 Correct 2653 ms 283060 KB Output is correct
81 Correct 653 ms 114048 KB Output is correct
82 Correct 650 ms 109808 KB Output is correct
83 Correct 825 ms 119828 KB Output is correct
84 Correct 669 ms 117076 KB Output is correct
85 Correct 666 ms 117876 KB Output is correct
86 Correct 803 ms 112872 KB Output is correct
87 Correct 699 ms 113772 KB Output is correct
88 Correct 683 ms 114828 KB Output is correct
89 Correct 691 ms 112640 KB Output is correct
90 Correct 161 ms 72360 KB Output is correct
91 Correct 639 ms 117084 KB Output is correct
92 Correct 895 ms 120520 KB Output is correct
93 Correct 841 ms 121524 KB Output is correct
94 Correct 855 ms 121112 KB Output is correct
95 Correct 729 ms 115252 KB Output is correct
96 Correct 209 ms 64380 KB Output is correct
97 Correct 4110 ms 371304 KB Output is correct
98 Correct 755 ms 89100 KB Output is correct
99 Execution timed out 5067 ms 389240 KB Time limit exceeded
100 Halted 0 ms 0 KB -