oj.uz

Submission #161054

# Submission time Handle Problem Language Result Execution time Memory
161054 2019-10-31T10:51:33 Z Minnakhmetov New Home (APIO18_new_home) C++14
100 / 100
 4786 ms 378772 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);
    }
}

void startSeg(int x, pair<int, int> y) {
    auto &p = mp[x][y];
    if (p.first == 0)
        p.second = cq;
    p.first++;
}
 
void endSeg(int x, pair<int, int> y) {
    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 || x == -INF && y == INF)
        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];
    }

    if (!t[v].empty()) {
        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 = 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 + 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) {
            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 updBetween(int, int, bool)':
new_home.cpp:60:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (x == y || x == -INF && y == INF)
                   ~~~~~~~~~~^~~~~~~~~~~
new_home.cpp: In function 'void calcAns(int, int, int)':
new_home.cpp:95:22: 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 93 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 54 ms 56764 KB Output is correct
5 Correct 55 ms 56952 KB Output is correct
6 Correct 56 ms 56900 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 56988 KB Output is correct
9 Correct 66 ms 57080 KB Output is correct
10 Correct 57 ms 57132 KB Output is correct
11 Correct 55 ms 57052 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 56 ms 56952 KB Output is correct
14 Correct 55 ms 56928 KB Output is correct
15 Correct 55 ms 56956 KB Output is correct
16 Correct 55 ms 57080 KB Output is correct
17 Correct 57 ms 56924 KB Output is correct
18 Correct 58 ms 56952 KB Output is correct
19 Correct 56 ms 57080 KB Output is correct
20 Correct 58 ms 56972 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 57 ms 57080 KB Output is correct
23 Correct 59 ms 57044 KB Output is correct
24 Correct 59 ms 57092 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 60 ms 56952 KB Output is correct
27 Correct 58 ms 56984 KB Output is correct
28 Correct 55 ms 56872 KB Output is correct
29 Correct 55 ms 56824 KB Output is correct
30 Correct 56 ms 56824 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 93 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 54 ms 56764 KB Output is correct
5 Correct 55 ms 56952 KB Output is correct
6 Correct 56 ms 56900 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 56988 KB Output is correct
9 Correct 66 ms 57080 KB Output is correct
10 Correct 57 ms 57132 KB Output is correct
11 Correct 55 ms 57052 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 56 ms 56952 KB Output is correct
14 Correct 55 ms 56928 KB Output is correct
15 Correct 55 ms 56956 KB Output is correct
16 Correct 55 ms 57080 KB Output is correct
17 Correct 57 ms 56924 KB Output is correct
18 Correct 58 ms 56952 KB Output is correct
19 Correct 56 ms 57080 KB Output is correct
20 Correct 58 ms 56972 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 57 ms 57080 KB Output is correct
23 Correct 59 ms 57044 KB Output is correct
24 Correct 59 ms 57092 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 60 ms 56952 KB Output is correct
27 Correct 58 ms 56984 KB Output is correct
28 Correct 55 ms 56872 KB Output is correct
29 Correct 55 ms 56824 KB Output is correct
30 Correct 56 ms 56824 KB Output is correct
31 Correct 795 ms 112924 KB Output is correct
32 Correct 162 ms 62560 KB Output is correct
33 Correct 756 ms 109396 KB Output is correct
34 Correct 700 ms 109772 KB Output is correct
35 Correct 797 ms 113012 KB Output is correct
36 Correct 753 ms 112804 KB Output is correct
37 Correct 517 ms 102740 KB Output is correct
38 Correct 527 ms 102612 KB Output is correct
39 Correct 423 ms 92928 KB Output is correct
40 Correct 423 ms 95028 KB Output is correct
41 Correct 592 ms 100564 KB Output is correct
42 Correct 611 ms 101068 KB Output is correct
43 Correct 143 ms 64448 KB Output is correct
44 Correct 624 ms 99688 KB Output is correct
45 Correct 574 ms 94388 KB Output is correct
46 Correct 468 ms 85352 KB Output is correct
47 Correct 311 ms 83292 KB Output is correct
48 Correct 303 ms 81748 KB Output is correct
49 Correct 366 ms 87892 KB Output is correct
50 Correct 463 ms 97392 KB Output is correct
51 Correct 394 ms 85636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2618 ms 171368 KB Output is correct
2 Correct 2523 ms 170736 KB Output is correct
3 Correct 2164 ms 191916 KB Output is correct
4 Correct 2801 ms 174444 KB Output is correct
5 Correct 2275 ms 167124 KB Output is correct
6 Correct 2425 ms 170172 KB Output is correct
7 Correct 2029 ms 192068 KB Output is correct
8 Correct 2119 ms 174784 KB Output is correct
9 Correct 2139 ms 172196 KB Output is correct
10 Correct 2109 ms 174364 KB Output is correct
11 Correct 1346 ms 171652 KB Output is correct
12 Correct 1491 ms 173224 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4025 ms 278272 KB Output is correct
2 Correct 675 ms 93120 KB Output is correct
3 Correct 4018 ms 277860 KB Output is correct
4 Correct 2703 ms 256320 KB Output is correct
5 Correct 3726 ms 272884 KB Output is correct
6 Correct 3803 ms 268648 KB Output is correct
7 Correct 3730 ms 276736 KB Output is correct
8 Correct 3905 ms 277496 KB Output is correct
9 Correct 2881 ms 255568 KB Output is correct
10 Correct 3551 ms 265240 KB Output is correct
11 Correct 3652 ms 276804 KB Output is correct
12 Correct 3678 ms 277308 KB Output is correct
13 Correct 1720 ms 226084 KB Output is correct
14 Correct 1710 ms 223524 KB Output is correct
15 Correct 2081 ms 241508 KB Output is correct
16 Correct 2442 ms 255012 KB Output is correct
17 Correct 2209 ms 249084 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 93 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 54 ms 56764 KB Output is correct
5 Correct 55 ms 56952 KB Output is correct
6 Correct 56 ms 56900 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 56988 KB Output is correct
9 Correct 66 ms 57080 KB Output is correct
10 Correct 57 ms 57132 KB Output is correct
11 Correct 55 ms 57052 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 56 ms 56952 KB Output is correct
14 Correct 55 ms 56928 KB Output is correct
15 Correct 55 ms 56956 KB Output is correct
16 Correct 55 ms 57080 KB Output is correct
17 Correct 57 ms 56924 KB Output is correct
18 Correct 58 ms 56952 KB Output is correct
19 Correct 56 ms 57080 KB Output is correct
20 Correct 58 ms 56972 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 57 ms 57080 KB Output is correct
23 Correct 59 ms 57044 KB Output is correct
24 Correct 59 ms 57092 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 60 ms 56952 KB Output is correct
27 Correct 58 ms 56984 KB Output is correct
28 Correct 55 ms 56872 KB Output is correct
29 Correct 55 ms 56824 KB Output is correct
30 Correct 56 ms 56824 KB Output is correct
31 Correct 795 ms 112924 KB Output is correct
32 Correct 162 ms 62560 KB Output is correct
33 Correct 756 ms 109396 KB Output is correct
34 Correct 700 ms 109772 KB Output is correct
35 Correct 797 ms 113012 KB Output is correct
36 Correct 753 ms 112804 KB Output is correct
37 Correct 517 ms 102740 KB Output is correct
38 Correct 527 ms 102612 KB Output is correct
39 Correct 423 ms 92928 KB Output is correct
40 Correct 423 ms 95028 KB Output is correct
41 Correct 592 ms 100564 KB Output is correct
42 Correct 611 ms 101068 KB Output is correct
43 Correct 143 ms 64448 KB Output is correct
44 Correct 624 ms 99688 KB Output is correct
45 Correct 574 ms 94388 KB Output is correct
46 Correct 468 ms 85352 KB Output is correct
47 Correct 311 ms 83292 KB Output is correct
48 Correct 303 ms 81748 KB Output is correct
49 Correct 366 ms 87892 KB Output is correct
50 Correct 463 ms 97392 KB Output is correct
51 Correct 394 ms 85636 KB Output is correct
52 Correct 611 ms 106324 KB Output is correct
53 Correct 553 ms 102336 KB Output is correct
54 Correct 739 ms 111316 KB Output is correct
55 Correct 594 ms 107092 KB Output is correct
56 Correct 575 ms 108652 KB Output is correct
57 Correct 606 ms 102528 KB Output is correct
58 Correct 630 ms 104304 KB Output is correct
59 Correct 618 ms 105920 KB Output is correct
60 Correct 640 ms 102200 KB Output is correct
61 Correct 144 ms 69984 KB Output is correct
62 Correct 547 ms 109172 KB Output is correct
63 Correct 704 ms 111496 KB Output is correct
64 Correct 699 ms 112416 KB Output is correct
65 Correct 731 ms 110964 KB Output is correct
66 Correct 651 ms 104340 KB Output is correct
67 Correct 186 ms 62640 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 56696 KB Output is correct
2 Correct 93 ms 56824 KB Output is correct
3 Correct 54 ms 56696 KB Output is correct
4 Correct 54 ms 56764 KB Output is correct
5 Correct 55 ms 56952 KB Output is correct
6 Correct 56 ms 56900 KB Output is correct
7 Correct 56 ms 56952 KB Output is correct
8 Correct 55 ms 56988 KB Output is correct
9 Correct 66 ms 57080 KB Output is correct
10 Correct 57 ms 57132 KB Output is correct
11 Correct 55 ms 57052 KB Output is correct
12 Correct 55 ms 56952 KB Output is correct
13 Correct 56 ms 56952 KB Output is correct
14 Correct 55 ms 56928 KB Output is correct
15 Correct 55 ms 56956 KB Output is correct
16 Correct 55 ms 57080 KB Output is correct
17 Correct 57 ms 56924 KB Output is correct
18 Correct 58 ms 56952 KB Output is correct
19 Correct 56 ms 57080 KB Output is correct
20 Correct 58 ms 56972 KB Output is correct
21 Correct 54 ms 56824 KB Output is correct
22 Correct 57 ms 57080 KB Output is correct
23 Correct 59 ms 57044 KB Output is correct
24 Correct 59 ms 57092 KB Output is correct
25 Correct 56 ms 56952 KB Output is correct
26 Correct 60 ms 56952 KB Output is correct
27 Correct 58 ms 56984 KB Output is correct
28 Correct 55 ms 56872 KB Output is correct
29 Correct 55 ms 56824 KB Output is correct
30 Correct 56 ms 56824 KB Output is correct
31 Correct 795 ms 112924 KB Output is correct
32 Correct 162 ms 62560 KB Output is correct
33 Correct 756 ms 109396 KB Output is correct
34 Correct 700 ms 109772 KB Output is correct
35 Correct 797 ms 113012 KB Output is correct
36 Correct 753 ms 112804 KB Output is correct
37 Correct 517 ms 102740 KB Output is correct
38 Correct 527 ms 102612 KB Output is correct
39 Correct 423 ms 92928 KB Output is correct
40 Correct 423 ms 95028 KB Output is correct
41 Correct 592 ms 100564 KB Output is correct
42 Correct 611 ms 101068 KB Output is correct
43 Correct 143 ms 64448 KB Output is correct
44 Correct 624 ms 99688 KB Output is correct
45 Correct 574 ms 94388 KB Output is correct
46 Correct 468 ms 85352 KB Output is correct
47 Correct 311 ms 83292 KB Output is correct
48 Correct 303 ms 81748 KB Output is correct
49 Correct 366 ms 87892 KB Output is correct
50 Correct 463 ms 97392 KB Output is correct
51 Correct 394 ms 85636 KB Output is correct
52 Correct 2618 ms 171368 KB Output is correct
53 Correct 2523 ms 170736 KB Output is correct
54 Correct 2164 ms 191916 KB Output is correct
55 Correct 2801 ms 174444 KB Output is correct
56 Correct 2275 ms 167124 KB Output is correct
57 Correct 2425 ms 170172 KB Output is correct
58 Correct 2029 ms 192068 KB Output is correct
59 Correct 2119 ms 174784 KB Output is correct
60 Correct 2139 ms 172196 KB Output is correct
61 Correct 2109 ms 174364 KB Output is correct
62 Correct 1346 ms 171652 KB Output is correct
63 Correct 1491 ms 173224 KB Output is correct
64 Correct 4025 ms 278272 KB Output is correct
65 Correct 675 ms 93120 KB Output is correct
66 Correct 4018 ms 277860 KB Output is correct
67 Correct 2703 ms 256320 KB Output is correct
68 Correct 3726 ms 272884 KB Output is correct
69 Correct 3803 ms 268648 KB Output is correct
70 Correct 3730 ms 276736 KB Output is correct
71 Correct 3905 ms 277496 KB Output is correct
72 Correct 2881 ms 255568 KB Output is correct
73 Correct 3551 ms 265240 KB Output is correct
74 Correct 3652 ms 276804 KB Output is correct
75 Correct 3678 ms 277308 KB Output is correct
76 Correct 1720 ms 226084 KB Output is correct
77 Correct 1710 ms 223524 KB Output is correct
78 Correct 2081 ms 241508 KB Output is correct
79 Correct 2442 ms 255012 KB Output is correct
80 Correct 2209 ms 249084 KB Output is correct
81 Correct 611 ms 106324 KB Output is correct
82 Correct 553 ms 102336 KB Output is correct
83 Correct 739 ms 111316 KB Output is correct
84 Correct 594 ms 107092 KB Output is correct
85 Correct 575 ms 108652 KB Output is correct
86 Correct 606 ms 102528 KB Output is correct
87 Correct 630 ms 104304 KB Output is correct
88 Correct 618 ms 105920 KB Output is correct
89 Correct 640 ms 102200 KB Output is correct
90 Correct 144 ms 69984 KB Output is correct
91 Correct 547 ms 109172 KB Output is correct
92 Correct 704 ms 111496 KB Output is correct
93 Correct 699 ms 112416 KB Output is correct
94 Correct 731 ms 110964 KB Output is correct
95 Correct 651 ms 104340 KB Output is correct
96 Correct 186 ms 62640 KB Output is correct
97 Correct 3918 ms 338424 KB Output is correct
98 Correct 674 ms 85648 KB Output is correct
99 Correct 4717 ms 346280 KB Output is correct
100 Correct 3491 ms 308112 KB Output is correct
101 Correct 4574 ms 365220 KB Output is correct
102 Correct 4759 ms 378772 KB Output is correct
103 Correct 3677 ms 328912 KB Output is correct
104 Correct 3534 ms 328228 KB Output is correct
105 Correct 2228 ms 285088 KB Output is correct
106 Correct 2352 ms 295792 KB Output is correct
107 Correct 3700 ms 341072 KB Output is correct
108 Correct 3566 ms 364960 KB Output is correct
109 Correct 3852 ms 317088 KB Output is correct
110 Correct 3881 ms 326240 KB Output is correct
111 Correct 3978 ms 334224 KB Output is correct
112 Correct 3918 ms 315776 KB Output is correct
113 Correct 541 ms 135928 KB Output is correct
114 Correct 3297 ms 344416 KB Output is correct
115 Correct 4281 ms 377288 KB Output is correct
116 Correct 4659 ms 377172 KB Output is correct
117 Correct 4786 ms 369980 KB Output is correct
118 Correct 4460 ms 334284 KB Output is correct
119 Correct 799 ms 92124 KB Output is correct
120 Correct 1355 ms 188708 KB Output is correct
121 Correct 1636 ms 212452 KB Output is correct
122 Correct 1528 ms 199900 KB Output is correct
123 Correct 1986 ms 230304 KB Output is correct
124 Correct 2528 ms 282576 KB Output is correct
125 Correct 1946 ms 217596 KB Output is correct
126 Correct 2519 ms 306096 KB Output is correct