oj.uz

Submission #161046

# Submission time Handle Problem Language Result Execution time Memory
161046 2019-10-31T10:17:32 Z Minnakhmetov New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 387416 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>, 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 m1 = lower_bound(all(vx), (x + y + 1) >> 1) - 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 55 ms 56780 KB Output is correct
2 Correct 54 ms 56692 KB Output is correct
3 Correct 55 ms 56788 KB Output is correct
4 Correct 55 ms 56748 KB Output is correct
5 Correct 58 ms 56780 KB Output is correct
6 Correct 59 ms 57024 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 57060 KB Output is correct
9 Correct 54 ms 57052 KB Output is correct
10 Correct 55 ms 57080 KB Output is correct
11 Correct 55 ms 56952 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 54 ms 56844 KB Output is correct
14 Correct 54 ms 56952 KB Output is correct
15 Correct 55 ms 56988 KB Output is correct
16 Correct 56 ms 57104 KB Output is correct
17 Correct 56 ms 57080 KB Output is correct
18 Correct 57 ms 57080 KB Output is correct
19 Correct 56 ms 57108 KB Output is correct
20 Correct 57 ms 57064 KB Output is correct
21 Correct 54 ms 56796 KB Output is correct
22 Correct 55 ms 57060 KB Output is correct
23 Correct 61 ms 57052 KB Output is correct
24 Correct 56 ms 57020 KB Output is correct
25 Correct 55 ms 57080 KB Output is correct
26 Correct 55 ms 57076 KB Output is correct
27 Correct 55 ms 56936 KB Output is correct
28 Correct 56 ms 56952 KB Output is correct
29 Correct 55 ms 56980 KB Output is correct
30 Correct 57 ms 56924 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 56780 KB Output is correct
2 Correct 54 ms 56692 KB Output is correct
3 Correct 55 ms 56788 KB Output is correct
4 Correct 55 ms 56748 KB Output is correct
5 Correct 58 ms 56780 KB Output is correct
6 Correct 59 ms 57024 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 57060 KB Output is correct
9 Correct 54 ms 57052 KB Output is correct
10 Correct 55 ms 57080 KB Output is correct
11 Correct 55 ms 56952 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 54 ms 56844 KB Output is correct
14 Correct 54 ms 56952 KB Output is correct
15 Correct 55 ms 56988 KB Output is correct
16 Correct 56 ms 57104 KB Output is correct
17 Correct 56 ms 57080 KB Output is correct
18 Correct 57 ms 57080 KB Output is correct
19 Correct 56 ms 57108 KB Output is correct
20 Correct 57 ms 57064 KB Output is correct
21 Correct 54 ms 56796 KB Output is correct
22 Correct 55 ms 57060 KB Output is correct
23 Correct 61 ms 57052 KB Output is correct
24 Correct 56 ms 57020 KB Output is correct
25 Correct 55 ms 57080 KB Output is correct
26 Correct 55 ms 57076 KB Output is correct
27 Correct 55 ms 56936 KB Output is correct
28 Correct 56 ms 56952 KB Output is correct
29 Correct 55 ms 56980 KB Output is correct
30 Correct 57 ms 56924 KB Output is correct
31 Correct 922 ms 122008 KB Output is correct
32 Correct 180 ms 63420 KB Output is correct
33 Correct 860 ms 118900 KB Output is correct
34 Correct 845 ms 119144 KB Output is correct
35 Correct 912 ms 121944 KB Output is correct
36 Correct 909 ms 121764 KB Output is correct
37 Correct 644 ms 113600 KB Output is correct
38 Correct 614 ms 113300 KB Output is correct
39 Correct 485 ms 103648 KB Output is correct
40 Correct 512 ms 105928 KB Output is correct
41 Correct 728 ms 111816 KB Output is correct
42 Correct 744 ms 112384 KB Output is correct
43 Correct 152 ms 66716 KB Output is correct
44 Correct 767 ms 111176 KB Output is correct
45 Correct 666 ms 105692 KB Output is correct
46 Correct 592 ms 96824 KB Output is correct
47 Correct 374 ms 93808 KB Output is correct
48 Correct 373 ms 92120 KB Output is correct
49 Correct 468 ms 98992 KB Output is correct
50 Correct 555 ms 108424 KB Output is correct
51 Correct 447 ms 96492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2999 ms 213872 KB Output is correct
2 Correct 2921 ms 210840 KB Output is correct
3 Correct 2625 ms 230692 KB Output is correct
4 Correct 2940 ms 214684 KB Output is correct
5 Correct 2733 ms 206268 KB Output is correct
6 Correct 3086 ms 208220 KB Output is correct
7 Correct 2560 ms 228080 KB Output is correct
8 Correct 2649 ms 213136 KB Output is correct
9 Correct 2424 ms 209292 KB Output is correct
10 Correct 2488 ms 211916 KB Output is correct
11 Correct 1739 ms 207440 KB Output is correct
12 Correct 1899 ms 209576 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4502 ms 312852 KB Output is correct
2 Correct 754 ms 96960 KB Output is correct
3 Correct 4510 ms 317016 KB Output is correct
4 Correct 3455 ms 292828 KB Output is correct
5 Correct 4577 ms 315460 KB Output is correct
6 Correct 4165 ms 310456 KB Output is correct
7 Correct 4162 ms 319792 KB Output is correct
8 Correct 4337 ms 320548 KB Output is correct
9 Correct 2984 ms 295448 KB Output is correct
10 Correct 3804 ms 307136 KB Output is correct
11 Correct 4220 ms 318776 KB Output is correct
12 Correct 4202 ms 319192 KB Output is correct
13 Correct 2123 ms 266644 KB Output is correct
14 Correct 2129 ms 263336 KB Output is correct
15 Correct 2403 ms 282540 KB Output is correct
16 Correct 2806 ms 297344 KB Output is correct
17 Correct 2616 ms 290200 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 56780 KB Output is correct
2 Correct 54 ms 56692 KB Output is correct
3 Correct 55 ms 56788 KB Output is correct
4 Correct 55 ms 56748 KB Output is correct
5 Correct 58 ms 56780 KB Output is correct
6 Correct 59 ms 57024 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 57060 KB Output is correct
9 Correct 54 ms 57052 KB Output is correct
10 Correct 55 ms 57080 KB Output is correct
11 Correct 55 ms 56952 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 54 ms 56844 KB Output is correct
14 Correct 54 ms 56952 KB Output is correct
15 Correct 55 ms 56988 KB Output is correct
16 Correct 56 ms 57104 KB Output is correct
17 Correct 56 ms 57080 KB Output is correct
18 Correct 57 ms 57080 KB Output is correct
19 Correct 56 ms 57108 KB Output is correct
20 Correct 57 ms 57064 KB Output is correct
21 Correct 54 ms 56796 KB Output is correct
22 Correct 55 ms 57060 KB Output is correct
23 Correct 61 ms 57052 KB Output is correct
24 Correct 56 ms 57020 KB Output is correct
25 Correct 55 ms 57080 KB Output is correct
26 Correct 55 ms 57076 KB Output is correct
27 Correct 55 ms 56936 KB Output is correct
28 Correct 56 ms 56952 KB Output is correct
29 Correct 55 ms 56980 KB Output is correct
30 Correct 57 ms 56924 KB Output is correct
31 Correct 922 ms 122008 KB Output is correct
32 Correct 180 ms 63420 KB Output is correct
33 Correct 860 ms 118900 KB Output is correct
34 Correct 845 ms 119144 KB Output is correct
35 Correct 912 ms 121944 KB Output is correct
36 Correct 909 ms 121764 KB Output is correct
37 Correct 644 ms 113600 KB Output is correct
38 Correct 614 ms 113300 KB Output is correct
39 Correct 485 ms 103648 KB Output is correct
40 Correct 512 ms 105928 KB Output is correct
41 Correct 728 ms 111816 KB Output is correct
42 Correct 744 ms 112384 KB Output is correct
43 Correct 152 ms 66716 KB Output is correct
44 Correct 767 ms 111176 KB Output is correct
45 Correct 666 ms 105692 KB Output is correct
46 Correct 592 ms 96824 KB Output is correct
47 Correct 374 ms 93808 KB Output is correct
48 Correct 373 ms 92120 KB Output is correct
49 Correct 468 ms 98992 KB Output is correct
50 Correct 555 ms 108424 KB Output is correct
51 Correct 447 ms 96492 KB Output is correct
52 Correct 614 ms 111868 KB Output is correct
53 Correct 625 ms 107744 KB Output is correct
54 Correct 898 ms 117812 KB Output is correct
55 Correct 661 ms 114688 KB Output is correct
56 Correct 656 ms 115844 KB Output is correct
57 Correct 707 ms 110596 KB Output is correct
58 Correct 698 ms 111540 KB Output is correct
59 Correct 703 ms 112892 KB Output is correct
60 Correct 710 ms 110292 KB Output is correct
61 Correct 158 ms 70640 KB Output is correct
62 Correct 640 ms 114960 KB Output is correct
63 Correct 787 ms 118364 KB Output is correct
64 Correct 805 ms 119520 KB Output is correct
65 Correct 840 ms 119224 KB Output is correct
66 Correct 723 ms 112876 KB Output is correct
67 Correct 196 ms 63176 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 56780 KB Output is correct
2 Correct 54 ms 56692 KB Output is correct
3 Correct 55 ms 56788 KB Output is correct
4 Correct 55 ms 56748 KB Output is correct
5 Correct 58 ms 56780 KB Output is correct
6 Correct 59 ms 57024 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 57060 KB Output is correct
9 Correct 54 ms 57052 KB Output is correct
10 Correct 55 ms 57080 KB Output is correct
11 Correct 55 ms 56952 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 54 ms 56844 KB Output is correct
14 Correct 54 ms 56952 KB Output is correct
15 Correct 55 ms 56988 KB Output is correct
16 Correct 56 ms 57104 KB Output is correct
17 Correct 56 ms 57080 KB Output is correct
18 Correct 57 ms 57080 KB Output is correct
19 Correct 56 ms 57108 KB Output is correct
20 Correct 57 ms 57064 KB Output is correct
21 Correct 54 ms 56796 KB Output is correct
22 Correct 55 ms 57060 KB Output is correct
23 Correct 61 ms 57052 KB Output is correct
24 Correct 56 ms 57020 KB Output is correct
25 Correct 55 ms 57080 KB Output is correct
26 Correct 55 ms 57076 KB Output is correct
27 Correct 55 ms 56936 KB Output is correct
28 Correct 56 ms 56952 KB Output is correct
29 Correct 55 ms 56980 KB Output is correct
30 Correct 57 ms 56924 KB Output is correct
31 Correct 922 ms 122008 KB Output is correct
32 Correct 180 ms 63420 KB Output is correct
33 Correct 860 ms 118900 KB Output is correct
34 Correct 845 ms 119144 KB Output is correct
35 Correct 912 ms 121944 KB Output is correct
36 Correct 909 ms 121764 KB Output is correct
37 Correct 644 ms 113600 KB Output is correct
38 Correct 614 ms 113300 KB Output is correct
39 Correct 485 ms 103648 KB Output is correct
40 Correct 512 ms 105928 KB Output is correct
41 Correct 728 ms 111816 KB Output is correct
42 Correct 744 ms 112384 KB Output is correct
43 Correct 152 ms 66716 KB Output is correct
44 Correct 767 ms 111176 KB Output is correct
45 Correct 666 ms 105692 KB Output is correct
46 Correct 592 ms 96824 KB Output is correct
47 Correct 374 ms 93808 KB Output is correct
48 Correct 373 ms 92120 KB Output is correct
49 Correct 468 ms 98992 KB Output is correct
50 Correct 555 ms 108424 KB Output is correct
51 Correct 447 ms 96492 KB Output is correct
52 Correct 2999 ms 213872 KB Output is correct
53 Correct 2921 ms 210840 KB Output is correct
54 Correct 2625 ms 230692 KB Output is correct
55 Correct 2940 ms 214684 KB Output is correct
56 Correct 2733 ms 206268 KB Output is correct
57 Correct 3086 ms 208220 KB Output is correct
58 Correct 2560 ms 228080 KB Output is correct
59 Correct 2649 ms 213136 KB Output is correct
60 Correct 2424 ms 209292 KB Output is correct
61 Correct 2488 ms 211916 KB Output is correct
62 Correct 1739 ms 207440 KB Output is correct
63 Correct 1899 ms 209576 KB Output is correct
64 Correct 4502 ms 312852 KB Output is correct
65 Correct 754 ms 96960 KB Output is correct
66 Correct 4510 ms 317016 KB Output is correct
67 Correct 3455 ms 292828 KB Output is correct
68 Correct 4577 ms 315460 KB Output is correct
69 Correct 4165 ms 310456 KB Output is correct
70 Correct 4162 ms 319792 KB Output is correct
71 Correct 4337 ms 320548 KB Output is correct
72 Correct 2984 ms 295448 KB Output is correct
73 Correct 3804 ms 307136 KB Output is correct
74 Correct 4220 ms 318776 KB Output is correct
75 Correct 4202 ms 319192 KB Output is correct
76 Correct 2123 ms 266644 KB Output is correct
77 Correct 2129 ms 263336 KB Output is correct
78 Correct 2403 ms 282540 KB Output is correct
79 Correct 2806 ms 297344 KB Output is correct
80 Correct 2616 ms 290200 KB Output is correct
81 Correct 614 ms 111868 KB Output is correct
82 Correct 625 ms 107744 KB Output is correct
83 Correct 898 ms 117812 KB Output is correct
84 Correct 661 ms 114688 KB Output is correct
85 Correct 656 ms 115844 KB Output is correct
86 Correct 707 ms 110596 KB Output is correct
87 Correct 698 ms 111540 KB Output is correct
88 Correct 703 ms 112892 KB Output is correct
89 Correct 710 ms 110292 KB Output is correct
90 Correct 158 ms 70640 KB Output is correct
91 Correct 640 ms 114960 KB Output is correct
92 Correct 787 ms 118364 KB Output is correct
93 Correct 805 ms 119520 KB Output is correct
94 Correct 840 ms 119224 KB Output is correct
95 Correct 723 ms 112876 KB Output is correct
96 Correct 196 ms 63176 KB Output is correct
97 Correct 3904 ms 374760 KB Output is correct
98 Correct 755 ms 88388 KB Output is correct
99 Execution timed out 5029 ms 387416 KB Time limit exceeded
100 Halted 0 ms 0 KB -