oj.uz

Submission #161050

# Submission time Handle Problem Language Result Execution time Memory
161050 2019-10-31T10:41:00 Z Minnakhmetov New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 392560 KB 
#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);
    }
}
 
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;
    auto &p = mp[x][y];
    if (p.first == 0)
        p.second = cq;
    p.first++;
}
 
void endSeg(int x, pair<int, int> y) {
    if (dummy(y.first) && dummy(y.second))
        return;
    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)
        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];
    }
 
    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;

    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 + 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:102: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:121: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 53 ms 56696 KB Output is correct
2 Correct 53 ms 56700 KB Output is correct
3 Correct 53 ms 56696 KB Output is correct
4 Correct 54 ms 56756 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56968 KB Output is correct
7 Correct 55 ms 56944 KB Output is correct
8 Correct 58 ms 56992 KB Output is correct
9 Correct 61 ms 56960 KB Output is correct
10 Correct 63 ms 56924 KB Output is correct
11 Correct 63 ms 57080 KB Output is correct
12 Correct 62 ms 56952 KB Output is correct
13 Correct 58 ms 56936 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 61 ms 57032 KB Output is correct
16 Correct 59 ms 56988 KB Output is correct
17 Correct 56 ms 56924 KB Output is correct
18 Correct 55 ms 56952 KB Output is correct
19 Correct 55 ms 56948 KB Output is correct
20 Correct 55 ms 56952 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 55 ms 56952 KB Output is correct
23 Correct 55 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 56 ms 56952 KB Output is correct
27 Correct 60 ms 56952 KB Output is correct
28 Correct 55 ms 56952 KB Output is correct
29 Correct 94 ms 56860 KB Output is correct
30 Correct 55 ms 56824 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56696 KB Output is correct
2 Correct 53 ms 56700 KB Output is correct
3 Correct 53 ms 56696 KB Output is correct
4 Correct 54 ms 56756 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56968 KB Output is correct
7 Correct 55 ms 56944 KB Output is correct
8 Correct 58 ms 56992 KB Output is correct
9 Correct 61 ms 56960 KB Output is correct
10 Correct 63 ms 56924 KB Output is correct
11 Correct 63 ms 57080 KB Output is correct
12 Correct 62 ms 56952 KB Output is correct
13 Correct 58 ms 56936 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 61 ms 57032 KB Output is correct
16 Correct 59 ms 56988 KB Output is correct
17 Correct 56 ms 56924 KB Output is correct
18 Correct 55 ms 56952 KB Output is correct
19 Correct 55 ms 56948 KB Output is correct
20 Correct 55 ms 56952 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 55 ms 56952 KB Output is correct
23 Correct 55 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 56 ms 56952 KB Output is correct
27 Correct 60 ms 56952 KB Output is correct
28 Correct 55 ms 56952 KB Output is correct
29 Correct 94 ms 56860 KB Output is correct
30 Correct 55 ms 56824 KB Output is correct
31 Correct 758 ms 112956 KB Output is correct
32 Correct 179 ms 62564 KB Output is correct
33 Correct 742 ms 109268 KB Output is correct
34 Correct 714 ms 109776 KB Output is correct
35 Correct 768 ms 113108 KB Output is correct
36 Correct 800 ms 112728 KB Output is correct
37 Correct 533 ms 102736 KB Output is correct
38 Correct 517 ms 102496 KB Output is correct
39 Correct 415 ms 92884 KB Output is correct
40 Correct 441 ms 95260 KB Output is correct
41 Correct 631 ms 100584 KB Output is correct
42 Correct 641 ms 101100 KB Output is correct
43 Correct 151 ms 64484 KB Output is correct
44 Correct 632 ms 99948 KB Output is correct
45 Correct 705 ms 94544 KB Output is correct
46 Correct 502 ms 85436 KB Output is correct
47 Correct 331 ms 83424 KB Output is correct
48 Correct 337 ms 81620 KB Output is correct
49 Correct 398 ms 88020 KB Output is correct
50 Correct 463 ms 97452 KB Output is correct
51 Correct 407 ms 85732 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2756 ms 171552 KB Output is correct
2 Correct 2620 ms 170816 KB Output is correct
3 Correct 2297 ms 191904 KB Output is correct
4 Correct 2665 ms 174304 KB Output is correct
5 Correct 2417 ms 167252 KB Output is correct
6 Correct 2535 ms 170324 KB Output is correct
7 Correct 2098 ms 191956 KB Output is correct
8 Correct 2354 ms 174844 KB Output is correct
9 Correct 2147 ms 172092 KB Output is correct
10 Correct 2195 ms 174312 KB Output is correct
11 Correct 1403 ms 171828 KB Output is correct
12 Correct 1547 ms 173076 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4022 ms 278244 KB Output is correct
2 Correct 711 ms 92968 KB Output is correct
3 Correct 4009 ms 277808 KB Output is correct
4 Correct 2854 ms 256072 KB Output is correct
5 Correct 4261 ms 272720 KB Output is correct
6 Correct 3828 ms 268876 KB Output is correct
7 Correct 3736 ms 276792 KB Output is correct
8 Correct 3897 ms 277488 KB Output is correct
9 Correct 2560 ms 255568 KB Output is correct
10 Correct 3644 ms 265240 KB Output is correct
11 Correct 3769 ms 276764 KB Output is correct
12 Correct 3790 ms 277352 KB Output is correct
13 Correct 2029 ms 225884 KB Output is correct
14 Correct 1769 ms 223628 KB Output is correct
15 Correct 2110 ms 241588 KB Output is correct
16 Correct 2353 ms 255064 KB Output is correct
17 Correct 2242 ms 248992 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56696 KB Output is correct
2 Correct 53 ms 56700 KB Output is correct
3 Correct 53 ms 56696 KB Output is correct
4 Correct 54 ms 56756 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56968 KB Output is correct
7 Correct 55 ms 56944 KB Output is correct
8 Correct 58 ms 56992 KB Output is correct
9 Correct 61 ms 56960 KB Output is correct
10 Correct 63 ms 56924 KB Output is correct
11 Correct 63 ms 57080 KB Output is correct
12 Correct 62 ms 56952 KB Output is correct
13 Correct 58 ms 56936 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 61 ms 57032 KB Output is correct
16 Correct 59 ms 56988 KB Output is correct
17 Correct 56 ms 56924 KB Output is correct
18 Correct 55 ms 56952 KB Output is correct
19 Correct 55 ms 56948 KB Output is correct
20 Correct 55 ms 56952 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 55 ms 56952 KB Output is correct
23 Correct 55 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 56 ms 56952 KB Output is correct
27 Correct 60 ms 56952 KB Output is correct
28 Correct 55 ms 56952 KB Output is correct
29 Correct 94 ms 56860 KB Output is correct
30 Correct 55 ms 56824 KB Output is correct
31 Correct 758 ms 112956 KB Output is correct
32 Correct 179 ms 62564 KB Output is correct
33 Correct 742 ms 109268 KB Output is correct
34 Correct 714 ms 109776 KB Output is correct
35 Correct 768 ms 113108 KB Output is correct
36 Correct 800 ms 112728 KB Output is correct
37 Correct 533 ms 102736 KB Output is correct
38 Correct 517 ms 102496 KB Output is correct
39 Correct 415 ms 92884 KB Output is correct
40 Correct 441 ms 95260 KB Output is correct
41 Correct 631 ms 100584 KB Output is correct
42 Correct 641 ms 101100 KB Output is correct
43 Correct 151 ms 64484 KB Output is correct
44 Correct 632 ms 99948 KB Output is correct
45 Correct 705 ms 94544 KB Output is correct
46 Correct 502 ms 85436 KB Output is correct
47 Correct 331 ms 83424 KB Output is correct
48 Correct 337 ms 81620 KB Output is correct
49 Correct 398 ms 88020 KB Output is correct
50 Correct 463 ms 97452 KB Output is correct
51 Correct 407 ms 85732 KB Output is correct
52 Correct 613 ms 106316 KB Output is correct
53 Correct 599 ms 102436 KB Output is correct
54 Correct 749 ms 111316 KB Output is correct
55 Correct 602 ms 107148 KB Output is correct
56 Correct 592 ms 108760 KB Output is correct
57 Correct 661 ms 102588 KB Output is correct
58 Correct 632 ms 104276 KB Output is correct
59 Correct 721 ms 106240 KB Output is correct
60 Correct 630 ms 102100 KB Output is correct
61 Correct 164 ms 70020 KB Output is correct
62 Correct 607 ms 109132 KB Output is correct
63 Correct 688 ms 111368 KB Output is correct
64 Correct 701 ms 112612 KB Output is correct
65 Correct 765 ms 110956 KB Output is correct
66 Correct 632 ms 104168 KB Output is correct
67 Correct 187 ms 62612 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56696 KB Output is correct
2 Correct 53 ms 56700 KB Output is correct
3 Correct 53 ms 56696 KB Output is correct
4 Correct 54 ms 56756 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56968 KB Output is correct
7 Correct 55 ms 56944 KB Output is correct
8 Correct 58 ms 56992 KB Output is correct
9 Correct 61 ms 56960 KB Output is correct
10 Correct 63 ms 56924 KB Output is correct
11 Correct 63 ms 57080 KB Output is correct
12 Correct 62 ms 56952 KB Output is correct
13 Correct 58 ms 56936 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 61 ms 57032 KB Output is correct
16 Correct 59 ms 56988 KB Output is correct
17 Correct 56 ms 56924 KB Output is correct
18 Correct 55 ms 56952 KB Output is correct
19 Correct 55 ms 56948 KB Output is correct
20 Correct 55 ms 56952 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 55 ms 56952 KB Output is correct
23 Correct 55 ms 57080 KB Output is correct
24 Correct 57 ms 57080 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 56 ms 56952 KB Output is correct
27 Correct 60 ms 56952 KB Output is correct
28 Correct 55 ms 56952 KB Output is correct
29 Correct 94 ms 56860 KB Output is correct
30 Correct 55 ms 56824 KB Output is correct
31 Correct 758 ms 112956 KB Output is correct
32 Correct 179 ms 62564 KB Output is correct
33 Correct 742 ms 109268 KB Output is correct
34 Correct 714 ms 109776 KB Output is correct
35 Correct 768 ms 113108 KB Output is correct
36 Correct 800 ms 112728 KB Output is correct
37 Correct 533 ms 102736 KB Output is correct
38 Correct 517 ms 102496 KB Output is correct
39 Correct 415 ms 92884 KB Output is correct
40 Correct 441 ms 95260 KB Output is correct
41 Correct 631 ms 100584 KB Output is correct
42 Correct 641 ms 101100 KB Output is correct
43 Correct 151 ms 64484 KB Output is correct
44 Correct 632 ms 99948 KB Output is correct
45 Correct 705 ms 94544 KB Output is correct
46 Correct 502 ms 85436 KB Output is correct
47 Correct 331 ms 83424 KB Output is correct
48 Correct 337 ms 81620 KB Output is correct
49 Correct 398 ms 88020 KB Output is correct
50 Correct 463 ms 97452 KB Output is correct
51 Correct 407 ms 85732 KB Output is correct
52 Correct 2756 ms 171552 KB Output is correct
53 Correct 2620 ms 170816 KB Output is correct
54 Correct 2297 ms 191904 KB Output is correct
55 Correct 2665 ms 174304 KB Output is correct
56 Correct 2417 ms 167252 KB Output is correct
57 Correct 2535 ms 170324 KB Output is correct
58 Correct 2098 ms 191956 KB Output is correct
59 Correct 2354 ms 174844 KB Output is correct
60 Correct 2147 ms 172092 KB Output is correct
61 Correct 2195 ms 174312 KB Output is correct
62 Correct 1403 ms 171828 KB Output is correct
63 Correct 1547 ms 173076 KB Output is correct
64 Correct 4022 ms 278244 KB Output is correct
65 Correct 711 ms 92968 KB Output is correct
66 Correct 4009 ms 277808 KB Output is correct
67 Correct 2854 ms 256072 KB Output is correct
68 Correct 4261 ms 272720 KB Output is correct
69 Correct 3828 ms 268876 KB Output is correct
70 Correct 3736 ms 276792 KB Output is correct
71 Correct 3897 ms 277488 KB Output is correct
72 Correct 2560 ms 255568 KB Output is correct
73 Correct 3644 ms 265240 KB Output is correct
74 Correct 3769 ms 276764 KB Output is correct
75 Correct 3790 ms 277352 KB Output is correct
76 Correct 2029 ms 225884 KB Output is correct
77 Correct 1769 ms 223628 KB Output is correct
78 Correct 2110 ms 241588 KB Output is correct
79 Correct 2353 ms 255064 KB Output is correct
80 Correct 2242 ms 248992 KB Output is correct
81 Correct 613 ms 106316 KB Output is correct
82 Correct 599 ms 102436 KB Output is correct
83 Correct 749 ms 111316 KB Output is correct
84 Correct 602 ms 107148 KB Output is correct
85 Correct 592 ms 108760 KB Output is correct
86 Correct 661 ms 102588 KB Output is correct
87 Correct 632 ms 104276 KB Output is correct
88 Correct 721 ms 106240 KB Output is correct
89 Correct 630 ms 102100 KB Output is correct
90 Correct 164 ms 70020 KB Output is correct
91 Correct 607 ms 109132 KB Output is correct
92 Correct 688 ms 111368 KB Output is correct
93 Correct 701 ms 112612 KB Output is correct
94 Correct 765 ms 110956 KB Output is correct
95 Correct 632 ms 104168 KB Output is correct
96 Correct 187 ms 62612 KB Output is correct
97 Correct 3588 ms 338444 KB Output is correct
98 Correct 748 ms 85568 KB Output is correct
99 Correct 4771 ms 346384 KB Output is correct
100 Correct 3585 ms 314740 KB Output is correct
101 Correct 4813 ms 370612 KB Output is correct
102 Execution timed out 5073 ms 392560 KB Time limit exceeded
103 Halted 0 ms 0 KB -