oj.uz

Submission #161038

# Submission time Handle Problem Language Result Execution time Memory
161038 2019-10-31T10:01:39 Z Minnakhmetov New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 383480 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]);
    }    

    i = int(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 - INF + 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) {
        if (e.t == 0) {
            auto it = occ[e.y].upper_bound(e.x);

            updBetween(*prev(it), *it, false);
            
            if (occ[e.y].size() == 2)
                types_on++;
 
            it = occ[e.y].insert(e.x);

            updBetween(*prev(it), e.x, true);
            updBetween(e.x, *next(it), true);
 
        }
        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) {
                ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 56696 KB Output is correct
2 Correct 53 ms 56696 KB Output is correct
3 Correct 54 ms 56740 KB Output is correct
4 Correct 54 ms 56844 KB Output is correct
5 Correct 58 ms 56824 KB Output is correct
6 Correct 54 ms 57000 KB Output is correct
7 Correct 64 ms 56952 KB Output is correct
8 Correct 54 ms 57092 KB Output is correct
9 Correct 58 ms 57080 KB Output is correct
10 Correct 55 ms 57052 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 55 ms 57136 KB Output is correct
13 Correct 66 ms 56952 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 59 ms 57080 KB Output is correct
16 Correct 56 ms 57080 KB Output is correct
17 Correct 55 ms 57016 KB Output is correct
18 Correct 56 ms 57080 KB Output is correct
19 Correct 61 ms 57012 KB Output is correct
20 Correct 61 ms 57080 KB Output is correct
21 Correct 59 ms 56828 KB Output is correct
22 Correct 54 ms 57080 KB Output is correct
23 Correct 54 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 61 ms 57080 KB Output is correct
26 Correct 61 ms 57024 KB Output is correct
27 Correct 57 ms 57080 KB Output is correct
28 Correct 60 ms 56916 KB Output is correct
29 Correct 59 ms 56952 KB Output is correct
30 Correct 61 ms 56924 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 56696 KB Output is correct
2 Correct 53 ms 56696 KB Output is correct
3 Correct 54 ms 56740 KB Output is correct
4 Correct 54 ms 56844 KB Output is correct
5 Correct 58 ms 56824 KB Output is correct
6 Correct 54 ms 57000 KB Output is correct
7 Correct 64 ms 56952 KB Output is correct
8 Correct 54 ms 57092 KB Output is correct
9 Correct 58 ms 57080 KB Output is correct
10 Correct 55 ms 57052 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 55 ms 57136 KB Output is correct
13 Correct 66 ms 56952 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 59 ms 57080 KB Output is correct
16 Correct 56 ms 57080 KB Output is correct
17 Correct 55 ms 57016 KB Output is correct
18 Correct 56 ms 57080 KB Output is correct
19 Correct 61 ms 57012 KB Output is correct
20 Correct 61 ms 57080 KB Output is correct
21 Correct 59 ms 56828 KB Output is correct
22 Correct 54 ms 57080 KB Output is correct
23 Correct 54 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 61 ms 57080 KB Output is correct
26 Correct 61 ms 57024 KB Output is correct
27 Correct 57 ms 57080 KB Output is correct
28 Correct 60 ms 56916 KB Output is correct
29 Correct 59 ms 56952 KB Output is correct
30 Correct 61 ms 56924 KB Output is correct
31 Correct 925 ms 120112 KB Output is correct
32 Correct 170 ms 62816 KB Output is correct
33 Correct 768 ms 117128 KB Output is correct
34 Correct 805 ms 117472 KB Output is correct
35 Correct 837 ms 120104 KB Output is correct
36 Correct 835 ms 119900 KB Output is correct
37 Correct 588 ms 110968 KB Output is correct
38 Correct 581 ms 110816 KB Output is correct
39 Correct 472 ms 101200 KB Output is correct
40 Correct 474 ms 103440 KB Output is correct
41 Correct 671 ms 109304 KB Output is correct
42 Correct 701 ms 109808 KB Output is correct
43 Correct 146 ms 64864 KB Output is correct
44 Correct 668 ms 108572 KB Output is correct
45 Correct 703 ms 103320 KB Output is correct
46 Correct 541 ms 95168 KB Output is correct
47 Correct 345 ms 92044 KB Output is correct
48 Correct 336 ms 90480 KB Output is correct
49 Correct 414 ms 97132 KB Output is correct
50 Correct 509 ms 106544 KB Output is correct
51 Correct 429 ms 94864 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3117 ms 205264 KB Output is correct
2 Correct 2847 ms 205764 KB Output is correct
3 Correct 2601 ms 223756 KB Output is correct
4 Correct 2945 ms 207796 KB Output is correct
5 Correct 2625 ms 201856 KB Output is correct
6 Correct 3099 ms 206832 KB Output is correct
7 Correct 2501 ms 225288 KB Output is correct
8 Correct 2530 ms 210544 KB Output is correct
9 Correct 2343 ms 208888 KB Output is correct
10 Correct 2701 ms 211876 KB Output is correct
11 Correct 1645 ms 208456 KB Output is correct
12 Correct 1829 ms 210240 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4742 ms 315540 KB Output is correct
2 Correct 743 ms 95624 KB Output is correct
3 Correct 4407 ms 312252 KB Output is correct
4 Correct 3395 ms 285268 KB Output is correct
5 Correct 4222 ms 306932 KB Output is correct
6 Correct 4065 ms 302172 KB Output is correct
7 Correct 4086 ms 311204 KB Output is correct
8 Correct 4255 ms 311632 KB Output is correct
9 Correct 2944 ms 284600 KB Output is correct
10 Correct 3798 ms 298372 KB Output is correct
11 Correct 4225 ms 310040 KB Output is correct
12 Correct 4129 ms 311608 KB Output is correct
13 Correct 2009 ms 259908 KB Output is correct
14 Correct 1972 ms 256896 KB Output is correct
15 Correct 2456 ms 274796 KB Output is correct
16 Correct 2655 ms 288432 KB Output is correct
17 Correct 2506 ms 281620 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 56696 KB Output is correct
2 Correct 53 ms 56696 KB Output is correct
3 Correct 54 ms 56740 KB Output is correct
4 Correct 54 ms 56844 KB Output is correct
5 Correct 58 ms 56824 KB Output is correct
6 Correct 54 ms 57000 KB Output is correct
7 Correct 64 ms 56952 KB Output is correct
8 Correct 54 ms 57092 KB Output is correct
9 Correct 58 ms 57080 KB Output is correct
10 Correct 55 ms 57052 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 55 ms 57136 KB Output is correct
13 Correct 66 ms 56952 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 59 ms 57080 KB Output is correct
16 Correct 56 ms 57080 KB Output is correct
17 Correct 55 ms 57016 KB Output is correct
18 Correct 56 ms 57080 KB Output is correct
19 Correct 61 ms 57012 KB Output is correct
20 Correct 61 ms 57080 KB Output is correct
21 Correct 59 ms 56828 KB Output is correct
22 Correct 54 ms 57080 KB Output is correct
23 Correct 54 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 61 ms 57080 KB Output is correct
26 Correct 61 ms 57024 KB Output is correct
27 Correct 57 ms 57080 KB Output is correct
28 Correct 60 ms 56916 KB Output is correct
29 Correct 59 ms 56952 KB Output is correct
30 Correct 61 ms 56924 KB Output is correct
31 Correct 925 ms 120112 KB Output is correct
32 Correct 170 ms 62816 KB Output is correct
33 Correct 768 ms 117128 KB Output is correct
34 Correct 805 ms 117472 KB Output is correct
35 Correct 837 ms 120104 KB Output is correct
36 Correct 835 ms 119900 KB Output is correct
37 Correct 588 ms 110968 KB Output is correct
38 Correct 581 ms 110816 KB Output is correct
39 Correct 472 ms 101200 KB Output is correct
40 Correct 474 ms 103440 KB Output is correct
41 Correct 671 ms 109304 KB Output is correct
42 Correct 701 ms 109808 KB Output is correct
43 Correct 146 ms 64864 KB Output is correct
44 Correct 668 ms 108572 KB Output is correct
45 Correct 703 ms 103320 KB Output is correct
46 Correct 541 ms 95168 KB Output is correct
47 Correct 345 ms 92044 KB Output is correct
48 Correct 336 ms 90480 KB Output is correct
49 Correct 414 ms 97132 KB Output is correct
50 Correct 509 ms 106544 KB Output is correct
51 Correct 429 ms 94864 KB Output is correct
52 Correct 630 ms 112784 KB Output is correct
53 Correct 605 ms 108772 KB Output is correct
54 Correct 764 ms 118612 KB Output is correct
55 Correct 666 ms 115736 KB Output is correct
56 Correct 622 ms 116612 KB Output is correct
57 Correct 669 ms 111664 KB Output is correct
58 Correct 824 ms 112492 KB Output is correct
59 Correct 695 ms 113620 KB Output is correct
60 Correct 702 ms 111264 KB Output is correct
61 Correct 164 ms 71392 KB Output is correct
62 Correct 615 ms 115736 KB Output is correct
63 Correct 775 ms 119388 KB Output is correct
64 Correct 780 ms 120428 KB Output is correct
65 Correct 806 ms 120020 KB Output is correct
66 Correct 702 ms 113720 KB Output is correct
67 Correct 192 ms 64096 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 56696 KB Output is correct
2 Correct 53 ms 56696 KB Output is correct
3 Correct 54 ms 56740 KB Output is correct
4 Correct 54 ms 56844 KB Output is correct
5 Correct 58 ms 56824 KB Output is correct
6 Correct 54 ms 57000 KB Output is correct
7 Correct 64 ms 56952 KB Output is correct
8 Correct 54 ms 57092 KB Output is correct
9 Correct 58 ms 57080 KB Output is correct
10 Correct 55 ms 57052 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 55 ms 57136 KB Output is correct
13 Correct 66 ms 56952 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 59 ms 57080 KB Output is correct
16 Correct 56 ms 57080 KB Output is correct
17 Correct 55 ms 57016 KB Output is correct
18 Correct 56 ms 57080 KB Output is correct
19 Correct 61 ms 57012 KB Output is correct
20 Correct 61 ms 57080 KB Output is correct
21 Correct 59 ms 56828 KB Output is correct
22 Correct 54 ms 57080 KB Output is correct
23 Correct 54 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 61 ms 57080 KB Output is correct
26 Correct 61 ms 57024 KB Output is correct
27 Correct 57 ms 57080 KB Output is correct
28 Correct 60 ms 56916 KB Output is correct
29 Correct 59 ms 56952 KB Output is correct
30 Correct 61 ms 56924 KB Output is correct
31 Correct 925 ms 120112 KB Output is correct
32 Correct 170 ms 62816 KB Output is correct
33 Correct 768 ms 117128 KB Output is correct
34 Correct 805 ms 117472 KB Output is correct
35 Correct 837 ms 120104 KB Output is correct
36 Correct 835 ms 119900 KB Output is correct
37 Correct 588 ms 110968 KB Output is correct
38 Correct 581 ms 110816 KB Output is correct
39 Correct 472 ms 101200 KB Output is correct
40 Correct 474 ms 103440 KB Output is correct
41 Correct 671 ms 109304 KB Output is correct
42 Correct 701 ms 109808 KB Output is correct
43 Correct 146 ms 64864 KB Output is correct
44 Correct 668 ms 108572 KB Output is correct
45 Correct 703 ms 103320 KB Output is correct
46 Correct 541 ms 95168 KB Output is correct
47 Correct 345 ms 92044 KB Output is correct
48 Correct 336 ms 90480 KB Output is correct
49 Correct 414 ms 97132 KB Output is correct
50 Correct 509 ms 106544 KB Output is correct
51 Correct 429 ms 94864 KB Output is correct
52 Correct 3117 ms 205264 KB Output is correct
53 Correct 2847 ms 205764 KB Output is correct
54 Correct 2601 ms 223756 KB Output is correct
55 Correct 2945 ms 207796 KB Output is correct
56 Correct 2625 ms 201856 KB Output is correct
57 Correct 3099 ms 206832 KB Output is correct
58 Correct 2501 ms 225288 KB Output is correct
59 Correct 2530 ms 210544 KB Output is correct
60 Correct 2343 ms 208888 KB Output is correct
61 Correct 2701 ms 211876 KB Output is correct
62 Correct 1645 ms 208456 KB Output is correct
63 Correct 1829 ms 210240 KB Output is correct
64 Correct 4742 ms 315540 KB Output is correct
65 Correct 743 ms 95624 KB Output is correct
66 Correct 4407 ms 312252 KB Output is correct
67 Correct 3395 ms 285268 KB Output is correct
68 Correct 4222 ms 306932 KB Output is correct
69 Correct 4065 ms 302172 KB Output is correct
70 Correct 4086 ms 311204 KB Output is correct
71 Correct 4255 ms 311632 KB Output is correct
72 Correct 2944 ms 284600 KB Output is correct
73 Correct 3798 ms 298372 KB Output is correct
74 Correct 4225 ms 310040 KB Output is correct
75 Correct 4129 ms 311608 KB Output is correct
76 Correct 2009 ms 259908 KB Output is correct
77 Correct 1972 ms 256896 KB Output is correct
78 Correct 2456 ms 274796 KB Output is correct
79 Correct 2655 ms 288432 KB Output is correct
80 Correct 2506 ms 281620 KB Output is correct
81 Correct 630 ms 112784 KB Output is correct
82 Correct 605 ms 108772 KB Output is correct
83 Correct 764 ms 118612 KB Output is correct
84 Correct 666 ms 115736 KB Output is correct
85 Correct 622 ms 116612 KB Output is correct
86 Correct 669 ms 111664 KB Output is correct
87 Correct 824 ms 112492 KB Output is correct
88 Correct 695 ms 113620 KB Output is correct
89 Correct 702 ms 111264 KB Output is correct
90 Correct 164 ms 71392 KB Output is correct
91 Correct 615 ms 115736 KB Output is correct
92 Correct 775 ms 119388 KB Output is correct
93 Correct 780 ms 120428 KB Output is correct
94 Correct 806 ms 120020 KB Output is correct
95 Correct 702 ms 113720 KB Output is correct
96 Correct 192 ms 64096 KB Output is correct
97 Correct 3862 ms 367780 KB Output is correct
98 Correct 803 ms 86468 KB Output is correct
99 Execution timed out 5102 ms 383480 KB Time limit exceeded
100 Halted 0 ms 0 KB -