oj.uz

Submission #161045

# Submission time Handle Problem Language Result Execution time Memory
161045 2019-10-31T10:16:43 Z Minnakhmetov New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 312972 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 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]);
    }    
 
    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: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:131: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 56696 KB Output is correct
2 Correct 54 ms 56672 KB Output is correct
3 Correct 54 ms 56824 KB Output is correct
4 Correct 56 ms 56700 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56952 KB Output is correct
7 Correct 55 ms 56952 KB Output is correct
8 Correct 55 ms 57056 KB Output is correct
9 Correct 54 ms 57208 KB Output is correct
10 Correct 54 ms 57080 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 54 ms 57012 KB Output is correct
13 Correct 55 ms 56964 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 57 ms 57080 KB Output is correct
16 Correct 57 ms 57040 KB Output is correct
17 Correct 57 ms 57080 KB Output is correct
18 Correct 56 ms 57196 KB Output is correct
19 Correct 59 ms 57208 KB Output is correct
20 Correct 86 ms 57032 KB Output is correct
21 Correct 55 ms 56824 KB Output is correct
22 Correct 56 ms 57080 KB Output is correct
23 Correct 62 ms 57080 KB Output is correct
24 Correct 57 ms 57160 KB Output is correct
25 Correct 59 ms 57080 KB Output is correct
26 Correct 55 ms 56984 KB Output is correct
27 Correct 56 ms 56952 KB Output is correct
28 Correct 56 ms 57032 KB Output is correct
29 Correct 55 ms 56952 KB Output is correct
30 Correct 55 ms 56952 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 56696 KB Output is correct
2 Correct 54 ms 56672 KB Output is correct
3 Correct 54 ms 56824 KB Output is correct
4 Correct 56 ms 56700 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56952 KB Output is correct
7 Correct 55 ms 56952 KB Output is correct
8 Correct 55 ms 57056 KB Output is correct
9 Correct 54 ms 57208 KB Output is correct
10 Correct 54 ms 57080 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 54 ms 57012 KB Output is correct
13 Correct 55 ms 56964 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 57 ms 57080 KB Output is correct
16 Correct 57 ms 57040 KB Output is correct
17 Correct 57 ms 57080 KB Output is correct
18 Correct 56 ms 57196 KB Output is correct
19 Correct 59 ms 57208 KB Output is correct
20 Correct 86 ms 57032 KB Output is correct
21 Correct 55 ms 56824 KB Output is correct
22 Correct 56 ms 57080 KB Output is correct
23 Correct 62 ms 57080 KB Output is correct
24 Correct 57 ms 57160 KB Output is correct
25 Correct 59 ms 57080 KB Output is correct
26 Correct 55 ms 56984 KB Output is correct
27 Correct 56 ms 56952 KB Output is correct
28 Correct 56 ms 57032 KB Output is correct
29 Correct 55 ms 56952 KB Output is correct
30 Correct 55 ms 56952 KB Output is correct
31 Correct 875 ms 121976 KB Output is correct
32 Correct 178 ms 63456 KB Output is correct
33 Correct 836 ms 118980 KB Output is correct
34 Correct 884 ms 119224 KB Output is correct
35 Correct 895 ms 122016 KB Output is correct
36 Correct 869 ms 121736 KB Output is correct
37 Correct 595 ms 112948 KB Output is correct
38 Correct 599 ms 112788 KB Output is correct
39 Correct 472 ms 103124 KB Output is correct
40 Correct 500 ms 105348 KB Output is correct
41 Correct 704 ms 111184 KB Output is correct
42 Correct 711 ms 111764 KB Output is correct
43 Correct 159 ms 66272 KB Output is correct
44 Correct 742 ms 110476 KB Output is correct
45 Correct 670 ms 105152 KB Output is correct
46 Correct 570 ms 96276 KB Output is correct
47 Correct 386 ms 93140 KB Output is correct
48 Correct 369 ms 91800 KB Output is correct
49 Correct 450 ms 98300 KB Output is correct
50 Correct 510 ms 107868 KB Output is correct
51 Correct 470 ms 95972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2959 ms 205916 KB Output is correct
2 Correct 3044 ms 204480 KB Output is correct
3 Correct 2924 ms 220548 KB Output is correct
4 Correct 3030 ms 204392 KB Output is correct
5 Correct 2775 ms 197564 KB Output is correct
6 Correct 2996 ms 201244 KB Output is correct
7 Correct 2599 ms 219944 KB Output is correct
8 Correct 2624 ms 205884 KB Output is correct
9 Correct 2506 ms 203340 KB Output is correct
10 Correct 2570 ms 206164 KB Output is correct
11 Correct 1689 ms 203624 KB Output is correct
12 Correct 1910 ms 205708 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5003 ms 312972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 56696 KB Output is correct
2 Correct 54 ms 56672 KB Output is correct
3 Correct 54 ms 56824 KB Output is correct
4 Correct 56 ms 56700 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56952 KB Output is correct
7 Correct 55 ms 56952 KB Output is correct
8 Correct 55 ms 57056 KB Output is correct
9 Correct 54 ms 57208 KB Output is correct
10 Correct 54 ms 57080 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 54 ms 57012 KB Output is correct
13 Correct 55 ms 56964 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 57 ms 57080 KB Output is correct
16 Correct 57 ms 57040 KB Output is correct
17 Correct 57 ms 57080 KB Output is correct
18 Correct 56 ms 57196 KB Output is correct
19 Correct 59 ms 57208 KB Output is correct
20 Correct 86 ms 57032 KB Output is correct
21 Correct 55 ms 56824 KB Output is correct
22 Correct 56 ms 57080 KB Output is correct
23 Correct 62 ms 57080 KB Output is correct
24 Correct 57 ms 57160 KB Output is correct
25 Correct 59 ms 57080 KB Output is correct
26 Correct 55 ms 56984 KB Output is correct
27 Correct 56 ms 56952 KB Output is correct
28 Correct 56 ms 57032 KB Output is correct
29 Correct 55 ms 56952 KB Output is correct
30 Correct 55 ms 56952 KB Output is correct
31 Correct 875 ms 121976 KB Output is correct
32 Correct 178 ms 63456 KB Output is correct
33 Correct 836 ms 118980 KB Output is correct
34 Correct 884 ms 119224 KB Output is correct
35 Correct 895 ms 122016 KB Output is correct
36 Correct 869 ms 121736 KB Output is correct
37 Correct 595 ms 112948 KB Output is correct
38 Correct 599 ms 112788 KB Output is correct
39 Correct 472 ms 103124 KB Output is correct
40 Correct 500 ms 105348 KB Output is correct
41 Correct 704 ms 111184 KB Output is correct
42 Correct 711 ms 111764 KB Output is correct
43 Correct 159 ms 66272 KB Output is correct
44 Correct 742 ms 110476 KB Output is correct
45 Correct 670 ms 105152 KB Output is correct
46 Correct 570 ms 96276 KB Output is correct
47 Correct 386 ms 93140 KB Output is correct
48 Correct 369 ms 91800 KB Output is correct
49 Correct 450 ms 98300 KB Output is correct
50 Correct 510 ms 107868 KB Output is correct
51 Correct 470 ms 95972 KB Output is correct
52 Correct 680 ms 114916 KB Output is correct
53 Correct 657 ms 110704 KB Output is correct
54 Correct 834 ms 120744 KB Output is correct
55 Correct 707 ms 117672 KB Output is correct
56 Correct 658 ms 118692 KB Output is correct
57 Correct 730 ms 113524 KB Output is correct
58 Correct 731 ms 114648 KB Output is correct
59 Correct 737 ms 115636 KB Output is correct
60 Correct 746 ms 113304 KB Output is correct
61 Correct 172 ms 72928 KB Output is correct
62 Correct 696 ms 117876 KB Output is correct
63 Correct 868 ms 121272 KB Output is correct
64 Correct 906 ms 122444 KB Output is correct
65 Correct 818 ms 121904 KB Output is correct
66 Correct 736 ms 115656 KB Output is correct
67 Correct 194 ms 64372 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 56696 KB Output is correct
2 Correct 54 ms 56672 KB Output is correct
3 Correct 54 ms 56824 KB Output is correct
4 Correct 56 ms 56700 KB Output is correct
5 Correct 54 ms 56824 KB Output is correct
6 Correct 55 ms 56952 KB Output is correct
7 Correct 55 ms 56952 KB Output is correct
8 Correct 55 ms 57056 KB Output is correct
9 Correct 54 ms 57208 KB Output is correct
10 Correct 54 ms 57080 KB Output is correct
11 Correct 54 ms 56952 KB Output is correct
12 Correct 54 ms 57012 KB Output is correct
13 Correct 55 ms 56964 KB Output is correct
14 Correct 56 ms 56952 KB Output is correct
15 Correct 57 ms 57080 KB Output is correct
16 Correct 57 ms 57040 KB Output is correct
17 Correct 57 ms 57080 KB Output is correct
18 Correct 56 ms 57196 KB Output is correct
19 Correct 59 ms 57208 KB Output is correct
20 Correct 86 ms 57032 KB Output is correct
21 Correct 55 ms 56824 KB Output is correct
22 Correct 56 ms 57080 KB Output is correct
23 Correct 62 ms 57080 KB Output is correct
24 Correct 57 ms 57160 KB Output is correct
25 Correct 59 ms 57080 KB Output is correct
26 Correct 55 ms 56984 KB Output is correct
27 Correct 56 ms 56952 KB Output is correct
28 Correct 56 ms 57032 KB Output is correct
29 Correct 55 ms 56952 KB Output is correct
30 Correct 55 ms 56952 KB Output is correct
31 Correct 875 ms 121976 KB Output is correct
32 Correct 178 ms 63456 KB Output is correct
33 Correct 836 ms 118980 KB Output is correct
34 Correct 884 ms 119224 KB Output is correct
35 Correct 895 ms 122016 KB Output is correct
36 Correct 869 ms 121736 KB Output is correct
37 Correct 595 ms 112948 KB Output is correct
38 Correct 599 ms 112788 KB Output is correct
39 Correct 472 ms 103124 KB Output is correct
40 Correct 500 ms 105348 KB Output is correct
41 Correct 704 ms 111184 KB Output is correct
42 Correct 711 ms 111764 KB Output is correct
43 Correct 159 ms 66272 KB Output is correct
44 Correct 742 ms 110476 KB Output is correct
45 Correct 670 ms 105152 KB Output is correct
46 Correct 570 ms 96276 KB Output is correct
47 Correct 386 ms 93140 KB Output is correct
48 Correct 369 ms 91800 KB Output is correct
49 Correct 450 ms 98300 KB Output is correct
50 Correct 510 ms 107868 KB Output is correct
51 Correct 470 ms 95972 KB Output is correct
52 Correct 2959 ms 205916 KB Output is correct
53 Correct 3044 ms 204480 KB Output is correct
54 Correct 2924 ms 220548 KB Output is correct
55 Correct 3030 ms 204392 KB Output is correct
56 Correct 2775 ms 197564 KB Output is correct
57 Correct 2996 ms 201244 KB Output is correct
58 Correct 2599 ms 219944 KB Output is correct
59 Correct 2624 ms 205884 KB Output is correct
60 Correct 2506 ms 203340 KB Output is correct
61 Correct 2570 ms 206164 KB Output is correct
62 Correct 1689 ms 203624 KB Output is correct
63 Correct 1910 ms 205708 KB Output is correct
64 Execution timed out 5003 ms 312972 KB Time limit exceeded
65 Halted 0 ms 0 KB -