oj.uz

Submission #161042

# Submission time Handle Problem Language Result Execution time Memory
161042 2019-10-31T10:10:19 Z Minnakhmetov New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 385960 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;
};

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

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];
unordered_map<pair<int, int>, vector<int>, HASH> 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) {
    mp[x][y].push_back(cq);
}
 
void endSeg(int x, pair<int, int> y) {
    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 || x == -INF && y == INF)
        return;

    int m = (x + y + 1) >> 1;
    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) {
        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 = L; j <= R; j++) {
        while (i < t[v].size() && t[v][i].first <= lt[j].first) {
            mx = max(mx, t[v][i].second.first);
            i++;
        }
        ans[lt[j].second] = max(ans[lt[j].second], mx - vx[lt[j].first]);
    }    

    i = int(t[v].size()) - 1, mx = -INF;
    for (int j = R; j >= L; j--) {
        while (i >= 0 && t[v][i].first > lt[j].first) {
            mx = max(mx, t[v][i].second.second);
            i--;
        }
        ans[lt[j].second] = max(ans[lt[j].second], mx - INF + vx[lt[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) {
        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 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:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < t[v].size() && t[v][i].first <= lt[j].first) {
                ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 59128 KB Output is correct
2 Correct 57 ms 59128 KB Output is correct
3 Correct 63 ms 59000 KB Output is correct
4 Correct 57 ms 59128 KB Output is correct
5 Correct 158 ms 59256 KB Output is correct
6 Correct 60 ms 59484 KB Output is correct
7 Correct 63 ms 59384 KB Output is correct
8 Correct 84 ms 59384 KB Output is correct
9 Correct 58 ms 59348 KB Output is correct
10 Correct 60 ms 59556 KB Output is correct
11 Correct 60 ms 59384 KB Output is correct
12 Correct 59 ms 59384 KB Output is correct
13 Correct 83 ms 59256 KB Output is correct
14 Correct 58 ms 59256 KB Output is correct
15 Correct 59 ms 59384 KB Output is correct
16 Correct 62 ms 59440 KB Output is correct
17 Correct 59 ms 59356 KB Output is correct
18 Correct 60 ms 59512 KB Output is correct
19 Correct 59 ms 59388 KB Output is correct
20 Correct 60 ms 59384 KB Output is correct
21 Correct 60 ms 59216 KB Output is correct
22 Correct 60 ms 59512 KB Output is correct
23 Correct 60 ms 59384 KB Output is correct
24 Correct 59 ms 59384 KB Output is correct
25 Correct 59 ms 59384 KB Output is correct
26 Correct 62 ms 59416 KB Output is correct
27 Correct 60 ms 59384 KB Output is correct
28 Correct 59 ms 59384 KB Output is correct
29 Correct 59 ms 59384 KB Output is correct
30 Correct 59 ms 59256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 59128 KB Output is correct
2 Correct 57 ms 59128 KB Output is correct
3 Correct 63 ms 59000 KB Output is correct
4 Correct 57 ms 59128 KB Output is correct
5 Correct 158 ms 59256 KB Output is correct
6 Correct 60 ms 59484 KB Output is correct
7 Correct 63 ms 59384 KB Output is correct
8 Correct 84 ms 59384 KB Output is correct
9 Correct 58 ms 59348 KB Output is correct
10 Correct 60 ms 59556 KB Output is correct
11 Correct 60 ms 59384 KB Output is correct
12 Correct 59 ms 59384 KB Output is correct
13 Correct 83 ms 59256 KB Output is correct
14 Correct 58 ms 59256 KB Output is correct
15 Correct 59 ms 59384 KB Output is correct
16 Correct 62 ms 59440 KB Output is correct
17 Correct 59 ms 59356 KB Output is correct
18 Correct 60 ms 59512 KB Output is correct
19 Correct 59 ms 59388 KB Output is correct
20 Correct 60 ms 59384 KB Output is correct
21 Correct 60 ms 59216 KB Output is correct
22 Correct 60 ms 59512 KB Output is correct
23 Correct 60 ms 59384 KB Output is correct
24 Correct 59 ms 59384 KB Output is correct
25 Correct 59 ms 59384 KB Output is correct
26 Correct 62 ms 59416 KB Output is correct
27 Correct 60 ms 59384 KB Output is correct
28 Correct 59 ms 59384 KB Output is correct
29 Correct 59 ms 59384 KB Output is correct
30 Correct 59 ms 59256 KB Output is correct
31 Correct 959 ms 124064 KB Output is correct
32 Correct 190 ms 65964 KB Output is correct
33 Correct 817 ms 121116 KB Output is correct
34 Correct 822 ms 121300 KB Output is correct
35 Correct 912 ms 123920 KB Output is correct
36 Correct 929 ms 123988 KB Output is correct
37 Correct 608 ms 115036 KB Output is correct
38 Correct 563 ms 114764 KB Output is correct
39 Correct 468 ms 105184 KB Output is correct
40 Correct 481 ms 107448 KB Output is correct
41 Correct 690 ms 112584 KB Output is correct
42 Correct 730 ms 113236 KB Output is correct
43 Correct 157 ms 68608 KB Output is correct
44 Correct 674 ms 111956 KB Output is correct
45 Correct 609 ms 106588 KB Output is correct
46 Correct 533 ms 97716 KB Output is correct
47 Correct 400 ms 94548 KB Output is correct
48 Correct 375 ms 93012 KB Output is correct
49 Correct 468 ms 99984 KB Output is correct
50 Correct 531 ms 109124 KB Output is correct
51 Correct 457 ms 97344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2793 ms 208468 KB Output is correct
2 Correct 3105 ms 210084 KB Output is correct
3 Correct 2263 ms 225256 KB Output is correct
4 Correct 2561 ms 210188 KB Output is correct
5 Correct 2846 ms 205032 KB Output is correct
6 Correct 3136 ms 206944 KB Output is correct
7 Correct 2036 ms 221832 KB Output is correct
8 Correct 2310 ms 211464 KB Output is correct
9 Correct 2732 ms 208708 KB Output is correct
10 Correct 2623 ms 210828 KB Output is correct
11 Correct 1721 ms 206896 KB Output is correct
12 Correct 2051 ms 207876 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4858 ms 313120 KB Output is correct
2 Correct 777 ms 95408 KB Output is correct
3 Correct 4464 ms 313048 KB Output is correct
4 Correct 2498 ms 284328 KB Output is correct
5 Correct 4335 ms 306572 KB Output is correct
6 Correct 3728 ms 300868 KB Output is correct
7 Correct 4119 ms 312576 KB Output is correct
8 Correct 4289 ms 313288 KB Output is correct
9 Correct 2348 ms 283612 KB Output is correct
10 Correct 3573 ms 297956 KB Output is correct
11 Correct 4230 ms 311048 KB Output is correct
12 Correct 4150 ms 312500 KB Output is correct
13 Correct 2327 ms 260296 KB Output is correct
14 Correct 2198 ms 257120 KB Output is correct
15 Correct 2653 ms 275880 KB Output is correct
16 Correct 2958 ms 290148 KB Output is correct
17 Correct 2581 ms 283376 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 59128 KB Output is correct
2 Correct 57 ms 59128 KB Output is correct
3 Correct 63 ms 59000 KB Output is correct
4 Correct 57 ms 59128 KB Output is correct
5 Correct 158 ms 59256 KB Output is correct
6 Correct 60 ms 59484 KB Output is correct
7 Correct 63 ms 59384 KB Output is correct
8 Correct 84 ms 59384 KB Output is correct
9 Correct 58 ms 59348 KB Output is correct
10 Correct 60 ms 59556 KB Output is correct
11 Correct 60 ms 59384 KB Output is correct
12 Correct 59 ms 59384 KB Output is correct
13 Correct 83 ms 59256 KB Output is correct
14 Correct 58 ms 59256 KB Output is correct
15 Correct 59 ms 59384 KB Output is correct
16 Correct 62 ms 59440 KB Output is correct
17 Correct 59 ms 59356 KB Output is correct
18 Correct 60 ms 59512 KB Output is correct
19 Correct 59 ms 59388 KB Output is correct
20 Correct 60 ms 59384 KB Output is correct
21 Correct 60 ms 59216 KB Output is correct
22 Correct 60 ms 59512 KB Output is correct
23 Correct 60 ms 59384 KB Output is correct
24 Correct 59 ms 59384 KB Output is correct
25 Correct 59 ms 59384 KB Output is correct
26 Correct 62 ms 59416 KB Output is correct
27 Correct 60 ms 59384 KB Output is correct
28 Correct 59 ms 59384 KB Output is correct
29 Correct 59 ms 59384 KB Output is correct
30 Correct 59 ms 59256 KB Output is correct
31 Correct 959 ms 124064 KB Output is correct
32 Correct 190 ms 65964 KB Output is correct
33 Correct 817 ms 121116 KB Output is correct
34 Correct 822 ms 121300 KB Output is correct
35 Correct 912 ms 123920 KB Output is correct
36 Correct 929 ms 123988 KB Output is correct
37 Correct 608 ms 115036 KB Output is correct
38 Correct 563 ms 114764 KB Output is correct
39 Correct 468 ms 105184 KB Output is correct
40 Correct 481 ms 107448 KB Output is correct
41 Correct 690 ms 112584 KB Output is correct
42 Correct 730 ms 113236 KB Output is correct
43 Correct 157 ms 68608 KB Output is correct
44 Correct 674 ms 111956 KB Output is correct
45 Correct 609 ms 106588 KB Output is correct
46 Correct 533 ms 97716 KB Output is correct
47 Correct 400 ms 94548 KB Output is correct
48 Correct 375 ms 93012 KB Output is correct
49 Correct 468 ms 99984 KB Output is correct
50 Correct 531 ms 109124 KB Output is correct
51 Correct 457 ms 97344 KB Output is correct
52 Correct 600 ms 114400 KB Output is correct
53 Correct 559 ms 110048 KB Output is correct
54 Correct 776 ms 119992 KB Output is correct
55 Correct 633 ms 117320 KB Output is correct
56 Correct 632 ms 118316 KB Output is correct
57 Correct 686 ms 112340 KB Output is correct
58 Correct 669 ms 114388 KB Output is correct
59 Correct 634 ms 115464 KB Output is correct
60 Correct 649 ms 112048 KB Output is correct
61 Correct 159 ms 72812 KB Output is correct
62 Correct 546 ms 117012 KB Output is correct
63 Correct 724 ms 120724 KB Output is correct
64 Correct 766 ms 122380 KB Output is correct
65 Correct 770 ms 120904 KB Output is correct
66 Correct 649 ms 114488 KB Output is correct
67 Correct 181 ms 65632 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 59128 KB Output is correct
2 Correct 57 ms 59128 KB Output is correct
3 Correct 63 ms 59000 KB Output is correct
4 Correct 57 ms 59128 KB Output is correct
5 Correct 158 ms 59256 KB Output is correct
6 Correct 60 ms 59484 KB Output is correct
7 Correct 63 ms 59384 KB Output is correct
8 Correct 84 ms 59384 KB Output is correct
9 Correct 58 ms 59348 KB Output is correct
10 Correct 60 ms 59556 KB Output is correct
11 Correct 60 ms 59384 KB Output is correct
12 Correct 59 ms 59384 KB Output is correct
13 Correct 83 ms 59256 KB Output is correct
14 Correct 58 ms 59256 KB Output is correct
15 Correct 59 ms 59384 KB Output is correct
16 Correct 62 ms 59440 KB Output is correct
17 Correct 59 ms 59356 KB Output is correct
18 Correct 60 ms 59512 KB Output is correct
19 Correct 59 ms 59388 KB Output is correct
20 Correct 60 ms 59384 KB Output is correct
21 Correct 60 ms 59216 KB Output is correct
22 Correct 60 ms 59512 KB Output is correct
23 Correct 60 ms 59384 KB Output is correct
24 Correct 59 ms 59384 KB Output is correct
25 Correct 59 ms 59384 KB Output is correct
26 Correct 62 ms 59416 KB Output is correct
27 Correct 60 ms 59384 KB Output is correct
28 Correct 59 ms 59384 KB Output is correct
29 Correct 59 ms 59384 KB Output is correct
30 Correct 59 ms 59256 KB Output is correct
31 Correct 959 ms 124064 KB Output is correct
32 Correct 190 ms 65964 KB Output is correct
33 Correct 817 ms 121116 KB Output is correct
34 Correct 822 ms 121300 KB Output is correct
35 Correct 912 ms 123920 KB Output is correct
36 Correct 929 ms 123988 KB Output is correct
37 Correct 608 ms 115036 KB Output is correct
38 Correct 563 ms 114764 KB Output is correct
39 Correct 468 ms 105184 KB Output is correct
40 Correct 481 ms 107448 KB Output is correct
41 Correct 690 ms 112584 KB Output is correct
42 Correct 730 ms 113236 KB Output is correct
43 Correct 157 ms 68608 KB Output is correct
44 Correct 674 ms 111956 KB Output is correct
45 Correct 609 ms 106588 KB Output is correct
46 Correct 533 ms 97716 KB Output is correct
47 Correct 400 ms 94548 KB Output is correct
48 Correct 375 ms 93012 KB Output is correct
49 Correct 468 ms 99984 KB Output is correct
50 Correct 531 ms 109124 KB Output is correct
51 Correct 457 ms 97344 KB Output is correct
52 Correct 2793 ms 208468 KB Output is correct
53 Correct 3105 ms 210084 KB Output is correct
54 Correct 2263 ms 225256 KB Output is correct
55 Correct 2561 ms 210188 KB Output is correct
56 Correct 2846 ms 205032 KB Output is correct
57 Correct 3136 ms 206944 KB Output is correct
58 Correct 2036 ms 221832 KB Output is correct
59 Correct 2310 ms 211464 KB Output is correct
60 Correct 2732 ms 208708 KB Output is correct
61 Correct 2623 ms 210828 KB Output is correct
62 Correct 1721 ms 206896 KB Output is correct
63 Correct 2051 ms 207876 KB Output is correct
64 Correct 4858 ms 313120 KB Output is correct
65 Correct 777 ms 95408 KB Output is correct
66 Correct 4464 ms 313048 KB Output is correct
67 Correct 2498 ms 284328 KB Output is correct
68 Correct 4335 ms 306572 KB Output is correct
69 Correct 3728 ms 300868 KB Output is correct
70 Correct 4119 ms 312576 KB Output is correct
71 Correct 4289 ms 313288 KB Output is correct
72 Correct 2348 ms 283612 KB Output is correct
73 Correct 3573 ms 297956 KB Output is correct
74 Correct 4230 ms 311048 KB Output is correct
75 Correct 4150 ms 312500 KB Output is correct
76 Correct 2327 ms 260296 KB Output is correct
77 Correct 2198 ms 257120 KB Output is correct
78 Correct 2653 ms 275880 KB Output is correct
79 Correct 2958 ms 290148 KB Output is correct
80 Correct 2581 ms 283376 KB Output is correct
81 Correct 600 ms 114400 KB Output is correct
82 Correct 559 ms 110048 KB Output is correct
83 Correct 776 ms 119992 KB Output is correct
84 Correct 633 ms 117320 KB Output is correct
85 Correct 632 ms 118316 KB Output is correct
86 Correct 686 ms 112340 KB Output is correct
87 Correct 669 ms 114388 KB Output is correct
88 Correct 634 ms 115464 KB Output is correct
89 Correct 649 ms 112048 KB Output is correct
90 Correct 159 ms 72812 KB Output is correct
91 Correct 546 ms 117012 KB Output is correct
92 Correct 724 ms 120724 KB Output is correct
93 Correct 766 ms 122380 KB Output is correct
94 Correct 770 ms 120904 KB Output is correct
95 Correct 649 ms 114488 KB Output is correct
96 Correct 181 ms 65632 KB Output is correct
97 Correct 3315 ms 366684 KB Output is correct
98 Correct 792 ms 87872 KB Output is correct
99 Execution timed out 5086 ms 385960 KB Time limit exceeded
100 Halted 0 ms 0 KB -