oj.uz

Submission #979739

# Submission time Handle Problem Language Result Execution time Memory
979739 2024-05-11T10:39:56 Z Jarif_Rahman New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 318676 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int lim = 7e6;

struct Node{
    int inc = -1e9, dec = -1e9;
    Node *l = nullptr, *r = nullptr;

    Node(){}
    Node(Node *_l, Node *_r): l(_l), r(_r){}
    void update(){
        inc = -1e9;
        if(l) inc = max(inc, l->inc);
        if(r) inc = max(inc, r->inc);

        dec = -1e9;
        if(l) dec = max(dec, l->dec);
        if(r) dec = max(dec, r->dec);
    }
}Nodes[lim];

int ls_node = 0;
Node* newNode(){
    return &Nodes[ls_node++];
}

struct sparse_segtree{
    Node* root = newNode();
    int n = 1;
    sparse_segtree(int _n){
        while(n < _n) n*=2;
    }
    void update(int i, Node *nd, int a, int b, int x, bool inc){
        if(a == b){
            if(inc) nd->inc = x+n-1-i;
            else nd->dec = x+i;
            return;
        }
        int m = (a+b)/2;
        if(i <= m){
            if(nd->l == nullptr) nd->l = newNode();
            update(i, nd->l, a, m, x, inc);
        }
        else{
             if(nd->r == nullptr) nd->r = newNode();
             update(i, nd->r, m+1, b, x, inc);
        }
        nd->update();
    }
    void update(int i, int x, bool inc){
        update(i, root, 0, n-1, x, inc);
    }

    int get(int l, int r, Node* nd, int a, int b, bool inc){
        if(!nd) return -1e9;
        if(a > r || b < l) return -1e9;
        if(a >= l && b <= r){
            if(inc) return nd->inc;
            else return nd->dec;
        }
        int m = (a+b)/2;
        return max(get(l, r, nd->l, a, m, inc), get(l, r, nd->r, m+1, b, inc));
    }
    int get(int l, int r, bool inc){
        return get(l, r, root, 0, n-1, inc);
    }
};

const int L = 1e8+5;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k, q; cin >> n >> k >> q;
    vector<tuple<int, int, int, int>> queries;

    for(int i = 0; i < n; i++){
        int x, t, a, b; cin >> x >> t >> a >> b; t--;
        queries.push_back({a, 0, x, t});
        queries.push_back({b, 2, x, t});
    }
    for(int i = 0; i < q; i++){
        int l, y; cin >> l >> y;
        queries.push_back({y, 1, l, i});
    }
    sort(queries.begin(), queries.end());

    vector<set<int>> stores(k);
    vector<map<int, int>> cnt(k);
    map<int, multiset<int>> mx[2];
    sparse_segtree S(L);

    auto add_to_mx = [&](int i, int x, bool inc){
        if(mx[inc][i].empty() || x > *mx[inc][i].rbegin()) S.update(i, x, inc);
        mx[inc][i].insert(x);
    };
    auto remove_from_mx = [&](int i, int x, bool inc){
        mx[inc][i].erase(mx[inc][i].find(x));
        if(mx[inc][i].empty()) S.update(i, -1e9, inc);
        else if(x > *mx[inc][i].rbegin()) S.update(i, *mx[inc][i].rbegin(), inc);
    };

    auto add = [&](int t, int x){
        cnt[t][x]++;
        if(cnt[t][x] > 1) return;
        auto it = stores[t].insert(x).first;
        if(stores[t].size() == 1){
            add_to_mx(0, x, false);
            add_to_mx(L-1, L-1-x, true);
        }
        else if(it == stores[t].begin()){
            remove_from_mx(0, *next(it), false);
            add_to_mx(0, x, false);
            int md = (x+*next(it))/2;
            if(md > x) add_to_mx(md, md-x, true);
            add_to_mx(md+1, *next(it)-md-1, false);
        }
        else if(next(it) == stores[t].end()){
            remove_from_mx(L-1, L-1-*prev(it), true);
            int md = (*prev(it)+x)/2;
            if(md > *prev(it)) add_to_mx(md, md-*prev(it), true);
            add_to_mx(md+1, x-md-1, false);
            add_to_mx(L-1, L-1-x, true);
        }
        else{
            int md = (*prev(it)+*next(it))/2;
            if(md > *prev(it)) remove_from_mx(md, md-*prev(it), true);
            remove_from_mx(md+1, *next(it)-md-1, false);

            md = (*prev(it)+x)/2;
            if(md > *prev(it)) add_to_mx(md, md-*prev(it), true);
            add_to_mx(md+1, x-md-1, false);

            md = (x+*next(it))/2;
            if(md > x) add_to_mx(md, md-x, true);
            add_to_mx(md+1, *next(it)-md-1, false);
        }
    };
    auto remove = [&](int t, int x){
        cnt[t][x]--;
        if(cnt[t][x] > 0) return;
        auto it = stores[t].find(x);
        if(stores[t].size() == 1){
            remove_from_mx(0, x, false);
            remove_from_mx(L-1, L-1-x, true);
        }
        else if(it == stores[t].begin()){
            add_to_mx(0, *next(it), false);
            remove_from_mx(0, x, false);
            int md = (x+*next(it))/2;
            if(md > x) remove_from_mx(md, md-x, true);
            remove_from_mx(md+1, *next(it)-md-1, false);
        }
        else if(next(it) == stores[t].end()){
            add_to_mx(L-1, L-1-*prev(it), true);
            int md = (*prev(it)+x)/2;
            if(md > *prev(it)) remove_from_mx(md, md-*prev(it), true);
            remove_from_mx(md+1, x-md-1, false);
            remove_from_mx(L-1, L-1-x, true);
        }
        else{
            int md = (*prev(it)+*next(it))/2;
            if(md > *prev(it)) add_to_mx(md, md-*prev(it), true);
            add_to_mx(md+1, *next(it)-md-1, false);

            md = (*prev(it)+x)/2;
            if(md > *prev(it)) remove_from_mx(md, md-*prev(it), true);
            remove_from_mx(md+1, x-md-1, false);

            md = (x+*next(it))/2;
            if(md > x) remove_from_mx(md, md-x, true);
            remove_from_mx(md+1, *next(it)-md-1, false);
        }
        stores[t].erase(it);
    };

    vector<int> cnt_t(k, 0);
    int nonzero = 0;

    vector<int> ans(q);

    for(auto [_, type, x, i]: queries){
        if(type == 0){
            cnt_t[i]++;
            if(cnt_t[i] == 1) nonzero++;
            add(i, x);
        }
        else if(type == 2){
            cnt_t[i]--;
            if(cnt_t[i] == 0) nonzero--;
            remove(i, x);
        }
        else{
            if(nonzero < k) ans[i] = -1;
            else ans[i] = max(S.get(0, x, 0)-x, S.get(x, S.n-1, 1)-(S.n-1)+x);
        }
    }

    for(int x: ans) cout << x << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 164692 KB Output is correct
2 Correct 30 ms 164772 KB Output is correct
3 Correct 29 ms 164620 KB Output is correct
4 Correct 26 ms 164700 KB Output is correct
5 Correct 27 ms 164856 KB Output is correct
6 Correct 29 ms 164956 KB Output is correct
7 Correct 27 ms 164720 KB Output is correct
8 Correct 28 ms 164956 KB Output is correct
9 Correct 28 ms 164976 KB Output is correct
10 Correct 29 ms 164956 KB Output is correct
11 Correct 31 ms 164900 KB Output is correct
12 Correct 29 ms 164956 KB Output is correct
13 Correct 29 ms 164948 KB Output is correct
14 Correct 27 ms 164692 KB Output is correct
15 Correct 28 ms 164944 KB Output is correct
16 Correct 28 ms 164948 KB Output is correct
17 Correct 27 ms 164952 KB Output is correct
18 Correct 28 ms 165168 KB Output is correct
19 Correct 29 ms 164952 KB Output is correct
20 Correct 28 ms 164956 KB Output is correct
21 Correct 29 ms 164892 KB Output is correct
22 Correct 27 ms 164952 KB Output is correct
23 Correct 28 ms 164948 KB Output is correct
24 Correct 29 ms 164944 KB Output is correct
25 Correct 30 ms 164776 KB Output is correct
26 Correct 29 ms 164900 KB Output is correct
27 Correct 28 ms 164716 KB Output is correct
28 Correct 29 ms 164684 KB Output is correct
29 Correct 28 ms 164956 KB Output is correct
30 Correct 28 ms 164864 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 164692 KB Output is correct
2 Correct 30 ms 164772 KB Output is correct
3 Correct 29 ms 164620 KB Output is correct
4 Correct 26 ms 164700 KB Output is correct
5 Correct 27 ms 164856 KB Output is correct
6 Correct 29 ms 164956 KB Output is correct
7 Correct 27 ms 164720 KB Output is correct
8 Correct 28 ms 164956 KB Output is correct
9 Correct 28 ms 164976 KB Output is correct
10 Correct 29 ms 164956 KB Output is correct
11 Correct 31 ms 164900 KB Output is correct
12 Correct 29 ms 164956 KB Output is correct
13 Correct 29 ms 164948 KB Output is correct
14 Correct 27 ms 164692 KB Output is correct
15 Correct 28 ms 164944 KB Output is correct
16 Correct 28 ms 164948 KB Output is correct
17 Correct 27 ms 164952 KB Output is correct
18 Correct 28 ms 165168 KB Output is correct
19 Correct 29 ms 164952 KB Output is correct
20 Correct 28 ms 164956 KB Output is correct
21 Correct 29 ms 164892 KB Output is correct
22 Correct 27 ms 164952 KB Output is correct
23 Correct 28 ms 164948 KB Output is correct
24 Correct 29 ms 164944 KB Output is correct
25 Correct 30 ms 164776 KB Output is correct
26 Correct 29 ms 164900 KB Output is correct
27 Correct 28 ms 164716 KB Output is correct
28 Correct 29 ms 164684 KB Output is correct
29 Correct 28 ms 164956 KB Output is correct
30 Correct 28 ms 164864 KB Output is correct
31 Correct 1072 ms 211048 KB Output is correct
32 Correct 78 ms 170668 KB Output is correct
33 Correct 1022 ms 205504 KB Output is correct
34 Correct 1085 ms 203596 KB Output is correct
35 Correct 1107 ms 210996 KB Output is correct
36 Correct 1052 ms 212112 KB Output is correct
37 Correct 673 ms 202400 KB Output is correct
38 Correct 662 ms 203612 KB Output is correct
39 Correct 543 ms 201920 KB Output is correct
40 Correct 557 ms 202320 KB Output is correct
41 Correct 437 ms 186616 KB Output is correct
42 Correct 478 ms 185948 KB Output is correct
43 Correct 76 ms 169420 KB Output is correct
44 Correct 443 ms 187372 KB Output is correct
45 Correct 438 ms 186560 KB Output is correct
46 Correct 419 ms 186048 KB Output is correct
47 Correct 266 ms 181952 KB Output is correct
48 Correct 267 ms 184124 KB Output is correct
49 Correct 297 ms 184892 KB Output is correct
50 Correct 304 ms 184780 KB Output is correct
51 Correct 332 ms 185064 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2686 ms 290832 KB Output is correct
2 Correct 1516 ms 294568 KB Output is correct
3 Correct 729 ms 268484 KB Output is correct
4 Correct 2420 ms 287224 KB Output is correct
5 Correct 1550 ms 294408 KB Output is correct
6 Correct 1512 ms 295580 KB Output is correct
7 Correct 680 ms 268960 KB Output is correct
8 Correct 2482 ms 288040 KB Output is correct
9 Correct 2781 ms 294120 KB Output is correct
10 Correct 1953 ms 294940 KB Output is correct
11 Correct 1440 ms 292964 KB Output is correct
12 Correct 1579 ms 294744 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 164692 KB Output is correct
2 Correct 30 ms 164772 KB Output is correct
3 Correct 29 ms 164620 KB Output is correct
4 Correct 26 ms 164700 KB Output is correct
5 Correct 27 ms 164856 KB Output is correct
6 Correct 29 ms 164956 KB Output is correct
7 Correct 27 ms 164720 KB Output is correct
8 Correct 28 ms 164956 KB Output is correct
9 Correct 28 ms 164976 KB Output is correct
10 Correct 29 ms 164956 KB Output is correct
11 Correct 31 ms 164900 KB Output is correct
12 Correct 29 ms 164956 KB Output is correct
13 Correct 29 ms 164948 KB Output is correct
14 Correct 27 ms 164692 KB Output is correct
15 Correct 28 ms 164944 KB Output is correct
16 Correct 28 ms 164948 KB Output is correct
17 Correct 27 ms 164952 KB Output is correct
18 Correct 28 ms 165168 KB Output is correct
19 Correct 29 ms 164952 KB Output is correct
20 Correct 28 ms 164956 KB Output is correct
21 Correct 29 ms 164892 KB Output is correct
22 Correct 27 ms 164952 KB Output is correct
23 Correct 28 ms 164948 KB Output is correct
24 Correct 29 ms 164944 KB Output is correct
25 Correct 30 ms 164776 KB Output is correct
26 Correct 29 ms 164900 KB Output is correct
27 Correct 28 ms 164716 KB Output is correct
28 Correct 29 ms 164684 KB Output is correct
29 Correct 28 ms 164956 KB Output is correct
30 Correct 28 ms 164864 KB Output is correct
31 Correct 1072 ms 211048 KB Output is correct
32 Correct 78 ms 170668 KB Output is correct
33 Correct 1022 ms 205504 KB Output is correct
34 Correct 1085 ms 203596 KB Output is correct
35 Correct 1107 ms 210996 KB Output is correct
36 Correct 1052 ms 212112 KB Output is correct
37 Correct 673 ms 202400 KB Output is correct
38 Correct 662 ms 203612 KB Output is correct
39 Correct 543 ms 201920 KB Output is correct
40 Correct 557 ms 202320 KB Output is correct
41 Correct 437 ms 186616 KB Output is correct
42 Correct 478 ms 185948 KB Output is correct
43 Correct 76 ms 169420 KB Output is correct
44 Correct 443 ms 187372 KB Output is correct
45 Correct 438 ms 186560 KB Output is correct
46 Correct 419 ms 186048 KB Output is correct
47 Correct 266 ms 181952 KB Output is correct
48 Correct 267 ms 184124 KB Output is correct
49 Correct 297 ms 184892 KB Output is correct
50 Correct 304 ms 184780 KB Output is correct
51 Correct 332 ms 185064 KB Output is correct
52 Correct 142 ms 186376 KB Output is correct
53 Correct 146 ms 179048 KB Output is correct
54 Correct 483 ms 191124 KB Output is correct
55 Correct 359 ms 186520 KB Output is correct
56 Correct 297 ms 186232 KB Output is correct
57 Correct 432 ms 186208 KB Output is correct
58 Correct 337 ms 185120 KB Output is correct
59 Correct 306 ms 183968 KB Output is correct
60 Correct 410 ms 186508 KB Output is correct
61 Correct 115 ms 186596 KB Output is correct
62 Correct 155 ms 185428 KB Output is correct
63 Correct 344 ms 186956 KB Output is correct
64 Correct 411 ms 187888 KB Output is correct
65 Correct 481 ms 187124 KB Output is correct
66 Correct 451 ms 186044 KB Output is correct
67 Correct 187 ms 173000 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 164692 KB Output is correct
2 Correct 30 ms 164772 KB Output is correct
3 Correct 29 ms 164620 KB Output is correct
4 Correct 26 ms 164700 KB Output is correct
5 Correct 27 ms 164856 KB Output is correct
6 Correct 29 ms 164956 KB Output is correct
7 Correct 27 ms 164720 KB Output is correct
8 Correct 28 ms 164956 KB Output is correct
9 Correct 28 ms 164976 KB Output is correct
10 Correct 29 ms 164956 KB Output is correct
11 Correct 31 ms 164900 KB Output is correct
12 Correct 29 ms 164956 KB Output is correct
13 Correct 29 ms 164948 KB Output is correct
14 Correct 27 ms 164692 KB Output is correct
15 Correct 28 ms 164944 KB Output is correct
16 Correct 28 ms 164948 KB Output is correct
17 Correct 27 ms 164952 KB Output is correct
18 Correct 28 ms 165168 KB Output is correct
19 Correct 29 ms 164952 KB Output is correct
20 Correct 28 ms 164956 KB Output is correct
21 Correct 29 ms 164892 KB Output is correct
22 Correct 27 ms 164952 KB Output is correct
23 Correct 28 ms 164948 KB Output is correct
24 Correct 29 ms 164944 KB Output is correct
25 Correct 30 ms 164776 KB Output is correct
26 Correct 29 ms 164900 KB Output is correct
27 Correct 28 ms 164716 KB Output is correct
28 Correct 29 ms 164684 KB Output is correct
29 Correct 28 ms 164956 KB Output is correct
30 Correct 28 ms 164864 KB Output is correct
31 Correct 1072 ms 211048 KB Output is correct
32 Correct 78 ms 170668 KB Output is correct
33 Correct 1022 ms 205504 KB Output is correct
34 Correct 1085 ms 203596 KB Output is correct
35 Correct 1107 ms 210996 KB Output is correct
36 Correct 1052 ms 212112 KB Output is correct
37 Correct 673 ms 202400 KB Output is correct
38 Correct 662 ms 203612 KB Output is correct
39 Correct 543 ms 201920 KB Output is correct
40 Correct 557 ms 202320 KB Output is correct
41 Correct 437 ms 186616 KB Output is correct
42 Correct 478 ms 185948 KB Output is correct
43 Correct 76 ms 169420 KB Output is correct
44 Correct 443 ms 187372 KB Output is correct
45 Correct 438 ms 186560 KB Output is correct
46 Correct 419 ms 186048 KB Output is correct
47 Correct 266 ms 181952 KB Output is correct
48 Correct 267 ms 184124 KB Output is correct
49 Correct 297 ms 184892 KB Output is correct
50 Correct 304 ms 184780 KB Output is correct
51 Correct 332 ms 185064 KB Output is correct
52 Correct 2686 ms 290832 KB Output is correct
53 Correct 1516 ms 294568 KB Output is correct
54 Correct 729 ms 268484 KB Output is correct
55 Correct 2420 ms 287224 KB Output is correct
56 Correct 1550 ms 294408 KB Output is correct
57 Correct 1512 ms 295580 KB Output is correct
58 Correct 680 ms 268960 KB Output is correct
59 Correct 2482 ms 288040 KB Output is correct
60 Correct 2781 ms 294120 KB Output is correct
61 Correct 1953 ms 294940 KB Output is correct
62 Correct 1440 ms 292964 KB Output is correct
63 Correct 1579 ms 294744 KB Output is correct
64 Execution timed out 5009 ms 318676 KB Time limit exceeded
65 Halted 0 ms 0 KB -