oj.uz

Submission #161037

# Submission time Handle Problem Language Result Execution time Memory
161037 2019-10-31T10:00:58 Z Minnakhmetov New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 386416 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 - 1 >= 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) {
        // cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
        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 56 ms 56696 KB Output is correct
2 Correct 53 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 55 ms 56824 KB Output is correct
5 Correct 61 ms 56824 KB Output is correct
6 Correct 64 ms 57080 KB Output is correct
7 Correct 64 ms 57056 KB Output is correct
8 Correct 65 ms 57052 KB Output is correct
9 Correct 64 ms 57080 KB Output is correct
10 Correct 63 ms 57080 KB Output is correct
11 Correct 63 ms 56952 KB Output is correct
12 Correct 63 ms 56952 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 62 ms 56952 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 62 ms 57080 KB Output is correct
17 Correct 64 ms 57080 KB Output is correct
18 Correct 65 ms 57080 KB Output is correct
19 Correct 63 ms 57044 KB Output is correct
20 Correct 62 ms 57080 KB Output is correct
21 Correct 62 ms 56824 KB Output is correct
22 Correct 63 ms 57080 KB Output is correct
23 Correct 63 ms 57020 KB Output is correct
24 Correct 63 ms 57080 KB Output is correct
25 Correct 63 ms 57080 KB Output is correct
26 Correct 62 ms 57076 KB Output is correct
27 Correct 61 ms 57028 KB Output is correct
28 Correct 57 ms 57080 KB Output is correct
29 Correct 61 ms 57160 KB Output is correct
30 Correct 54 ms 56952 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56696 KB Output is correct
2 Correct 53 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 55 ms 56824 KB Output is correct
5 Correct 61 ms 56824 KB Output is correct
6 Correct 64 ms 57080 KB Output is correct
7 Correct 64 ms 57056 KB Output is correct
8 Correct 65 ms 57052 KB Output is correct
9 Correct 64 ms 57080 KB Output is correct
10 Correct 63 ms 57080 KB Output is correct
11 Correct 63 ms 56952 KB Output is correct
12 Correct 63 ms 56952 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 62 ms 56952 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 62 ms 57080 KB Output is correct
17 Correct 64 ms 57080 KB Output is correct
18 Correct 65 ms 57080 KB Output is correct
19 Correct 63 ms 57044 KB Output is correct
20 Correct 62 ms 57080 KB Output is correct
21 Correct 62 ms 56824 KB Output is correct
22 Correct 63 ms 57080 KB Output is correct
23 Correct 63 ms 57020 KB Output is correct
24 Correct 63 ms 57080 KB Output is correct
25 Correct 63 ms 57080 KB Output is correct
26 Correct 62 ms 57076 KB Output is correct
27 Correct 61 ms 57028 KB Output is correct
28 Correct 57 ms 57080 KB Output is correct
29 Correct 61 ms 57160 KB Output is correct
30 Correct 54 ms 56952 KB Output is correct
31 Correct 973 ms 121344 KB Output is correct
32 Correct 175 ms 63584 KB Output is correct
33 Correct 800 ms 118252 KB Output is correct
34 Correct 802 ms 118760 KB Output is correct
35 Correct 890 ms 121448 KB Output is correct
36 Correct 810 ms 121212 KB Output is correct
37 Correct 560 ms 112152 KB Output is correct
38 Correct 568 ms 111976 KB Output is correct
39 Correct 462 ms 102220 KB Output is correct
40 Correct 473 ms 104532 KB Output is correct
41 Correct 675 ms 110420 KB Output is correct
42 Correct 728 ms 110904 KB Output is correct
43 Correct 155 ms 65508 KB Output is correct
44 Correct 680 ms 109768 KB Output is correct
45 Correct 666 ms 104412 KB Output is correct
46 Correct 553 ms 95292 KB Output is correct
47 Correct 354 ms 92508 KB Output is correct
48 Correct 344 ms 90804 KB Output is correct
49 Correct 416 ms 97660 KB Output is correct
50 Correct 495 ms 107028 KB Output is correct
51 Correct 420 ms 95252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3161 ms 206800 KB Output is correct
2 Correct 3053 ms 205924 KB Output is correct
3 Correct 2613 ms 223688 KB Output is correct
4 Correct 3132 ms 207776 KB Output is correct
5 Correct 2996 ms 200896 KB Output is correct
6 Correct 3128 ms 204824 KB Output is correct
7 Correct 2428 ms 223272 KB Output is correct
8 Correct 2539 ms 210104 KB Output is correct
9 Correct 2518 ms 207400 KB Output is correct
10 Correct 2495 ms 209932 KB Output is correct
11 Correct 1646 ms 206872 KB Output is correct
12 Correct 1866 ms 208476 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4478 ms 313936 KB Output is correct
2 Correct 719 ms 95508 KB Output is correct
3 Correct 4474 ms 312728 KB Output is correct
4 Correct 3135 ms 287476 KB Output is correct
5 Correct 4150 ms 308272 KB Output is correct
6 Correct 4064 ms 303940 KB Output is correct
7 Correct 4203 ms 313168 KB Output is correct
8 Correct 4263 ms 313692 KB Output is correct
9 Correct 3062 ms 287200 KB Output is correct
10 Correct 3856 ms 299820 KB Output is correct
11 Correct 4283 ms 311484 KB Output is correct
12 Correct 4197 ms 312208 KB Output is correct
13 Correct 2032 ms 260664 KB Output is correct
14 Correct 1976 ms 257204 KB Output is correct
15 Correct 2328 ms 275712 KB Output is correct
16 Correct 2694 ms 290308 KB Output is correct
17 Correct 2573 ms 283380 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56696 KB Output is correct
2 Correct 53 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 55 ms 56824 KB Output is correct
5 Correct 61 ms 56824 KB Output is correct
6 Correct 64 ms 57080 KB Output is correct
7 Correct 64 ms 57056 KB Output is correct
8 Correct 65 ms 57052 KB Output is correct
9 Correct 64 ms 57080 KB Output is correct
10 Correct 63 ms 57080 KB Output is correct
11 Correct 63 ms 56952 KB Output is correct
12 Correct 63 ms 56952 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 62 ms 56952 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 62 ms 57080 KB Output is correct
17 Correct 64 ms 57080 KB Output is correct
18 Correct 65 ms 57080 KB Output is correct
19 Correct 63 ms 57044 KB Output is correct
20 Correct 62 ms 57080 KB Output is correct
21 Correct 62 ms 56824 KB Output is correct
22 Correct 63 ms 57080 KB Output is correct
23 Correct 63 ms 57020 KB Output is correct
24 Correct 63 ms 57080 KB Output is correct
25 Correct 63 ms 57080 KB Output is correct
26 Correct 62 ms 57076 KB Output is correct
27 Correct 61 ms 57028 KB Output is correct
28 Correct 57 ms 57080 KB Output is correct
29 Correct 61 ms 57160 KB Output is correct
30 Correct 54 ms 56952 KB Output is correct
31 Correct 973 ms 121344 KB Output is correct
32 Correct 175 ms 63584 KB Output is correct
33 Correct 800 ms 118252 KB Output is correct
34 Correct 802 ms 118760 KB Output is correct
35 Correct 890 ms 121448 KB Output is correct
36 Correct 810 ms 121212 KB Output is correct
37 Correct 560 ms 112152 KB Output is correct
38 Correct 568 ms 111976 KB Output is correct
39 Correct 462 ms 102220 KB Output is correct
40 Correct 473 ms 104532 KB Output is correct
41 Correct 675 ms 110420 KB Output is correct
42 Correct 728 ms 110904 KB Output is correct
43 Correct 155 ms 65508 KB Output is correct
44 Correct 680 ms 109768 KB Output is correct
45 Correct 666 ms 104412 KB Output is correct
46 Correct 553 ms 95292 KB Output is correct
47 Correct 354 ms 92508 KB Output is correct
48 Correct 344 ms 90804 KB Output is correct
49 Correct 416 ms 97660 KB Output is correct
50 Correct 495 ms 107028 KB Output is correct
51 Correct 420 ms 95252 KB Output is correct
52 Correct 611 ms 114908 KB Output is correct
53 Correct 643 ms 110840 KB Output is correct
54 Correct 785 ms 120748 KB Output is correct
55 Correct 674 ms 117688 KB Output is correct
56 Correct 644 ms 118716 KB Output is correct
57 Correct 690 ms 113604 KB Output is correct
58 Correct 674 ms 114604 KB Output is correct
59 Correct 690 ms 115732 KB Output is correct
60 Correct 687 ms 113208 KB Output is correct
61 Correct 156 ms 72924 KB Output is correct
62 Correct 630 ms 117972 KB Output is correct
63 Correct 769 ms 121308 KB Output is correct
64 Correct 791 ms 122464 KB Output is correct
65 Correct 811 ms 122108 KB Output is correct
66 Correct 723 ms 115668 KB Output is correct
67 Correct 189 ms 64352 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56696 KB Output is correct
2 Correct 53 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 55 ms 56824 KB Output is correct
5 Correct 61 ms 56824 KB Output is correct
6 Correct 64 ms 57080 KB Output is correct
7 Correct 64 ms 57056 KB Output is correct
8 Correct 65 ms 57052 KB Output is correct
9 Correct 64 ms 57080 KB Output is correct
10 Correct 63 ms 57080 KB Output is correct
11 Correct 63 ms 56952 KB Output is correct
12 Correct 63 ms 56952 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 62 ms 56952 KB Output is correct
15 Correct 63 ms 57080 KB Output is correct
16 Correct 62 ms 57080 KB Output is correct
17 Correct 64 ms 57080 KB Output is correct
18 Correct 65 ms 57080 KB Output is correct
19 Correct 63 ms 57044 KB Output is correct
20 Correct 62 ms 57080 KB Output is correct
21 Correct 62 ms 56824 KB Output is correct
22 Correct 63 ms 57080 KB Output is correct
23 Correct 63 ms 57020 KB Output is correct
24 Correct 63 ms 57080 KB Output is correct
25 Correct 63 ms 57080 KB Output is correct
26 Correct 62 ms 57076 KB Output is correct
27 Correct 61 ms 57028 KB Output is correct
28 Correct 57 ms 57080 KB Output is correct
29 Correct 61 ms 57160 KB Output is correct
30 Correct 54 ms 56952 KB Output is correct
31 Correct 973 ms 121344 KB Output is correct
32 Correct 175 ms 63584 KB Output is correct
33 Correct 800 ms 118252 KB Output is correct
34 Correct 802 ms 118760 KB Output is correct
35 Correct 890 ms 121448 KB Output is correct
36 Correct 810 ms 121212 KB Output is correct
37 Correct 560 ms 112152 KB Output is correct
38 Correct 568 ms 111976 KB Output is correct
39 Correct 462 ms 102220 KB Output is correct
40 Correct 473 ms 104532 KB Output is correct
41 Correct 675 ms 110420 KB Output is correct
42 Correct 728 ms 110904 KB Output is correct
43 Correct 155 ms 65508 KB Output is correct
44 Correct 680 ms 109768 KB Output is correct
45 Correct 666 ms 104412 KB Output is correct
46 Correct 553 ms 95292 KB Output is correct
47 Correct 354 ms 92508 KB Output is correct
48 Correct 344 ms 90804 KB Output is correct
49 Correct 416 ms 97660 KB Output is correct
50 Correct 495 ms 107028 KB Output is correct
51 Correct 420 ms 95252 KB Output is correct
52 Correct 3161 ms 206800 KB Output is correct
53 Correct 3053 ms 205924 KB Output is correct
54 Correct 2613 ms 223688 KB Output is correct
55 Correct 3132 ms 207776 KB Output is correct
56 Correct 2996 ms 200896 KB Output is correct
57 Correct 3128 ms 204824 KB Output is correct
58 Correct 2428 ms 223272 KB Output is correct
59 Correct 2539 ms 210104 KB Output is correct
60 Correct 2518 ms 207400 KB Output is correct
61 Correct 2495 ms 209932 KB Output is correct
62 Correct 1646 ms 206872 KB Output is correct
63 Correct 1866 ms 208476 KB Output is correct
64 Correct 4478 ms 313936 KB Output is correct
65 Correct 719 ms 95508 KB Output is correct
66 Correct 4474 ms 312728 KB Output is correct
67 Correct 3135 ms 287476 KB Output is correct
68 Correct 4150 ms 308272 KB Output is correct
69 Correct 4064 ms 303940 KB Output is correct
70 Correct 4203 ms 313168 KB Output is correct
71 Correct 4263 ms 313692 KB Output is correct
72 Correct 3062 ms 287200 KB Output is correct
73 Correct 3856 ms 299820 KB Output is correct
74 Correct 4283 ms 311484 KB Output is correct
75 Correct 4197 ms 312208 KB Output is correct
76 Correct 2032 ms 260664 KB Output is correct
77 Correct 1976 ms 257204 KB Output is correct
78 Correct 2328 ms 275712 KB Output is correct
79 Correct 2694 ms 290308 KB Output is correct
80 Correct 2573 ms 283380 KB Output is correct
81 Correct 611 ms 114908 KB Output is correct
82 Correct 643 ms 110840 KB Output is correct
83 Correct 785 ms 120748 KB Output is correct
84 Correct 674 ms 117688 KB Output is correct
85 Correct 644 ms 118716 KB Output is correct
86 Correct 690 ms 113604 KB Output is correct
87 Correct 674 ms 114604 KB Output is correct
88 Correct 690 ms 115732 KB Output is correct
89 Correct 687 ms 113208 KB Output is correct
90 Correct 156 ms 72924 KB Output is correct
91 Correct 630 ms 117972 KB Output is correct
92 Correct 769 ms 121308 KB Output is correct
93 Correct 791 ms 122464 KB Output is correct
94 Correct 811 ms 122108 KB Output is correct
95 Correct 723 ms 115668 KB Output is correct
96 Correct 189 ms 64352 KB Output is correct
97 Correct 3972 ms 369496 KB Output is correct
98 Correct 764 ms 89388 KB Output is correct
99 Execution timed out 5095 ms 386416 KB Time limit exceeded
100 Halted 0 ms 0 KB -