oj.uz

Submission #979764

# Submission time Handle Problem Language Result Execution time Memory
979764 2024-05-11T10:51:02 Z Jarif_Rahman New Home (APIO18_new_home) C++17
57 / 100
 3708 ms 541720 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 = 5e6;

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<<=1;
    }
    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)>>1;
        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)>>1;
        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, map<int, 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()->first) S.update(i, x, inc);
        mx[inc][i][x]++;
    };
    auto remove_from_mx = [&](int i, int x, bool inc){
        mx[inc][i][x]--;
        if(mx[inc][i][x] == 0) mx[inc][i].erase(x);
        if(mx[inc][i].empty()) S.update(i, -1e9, inc);
        else if(x > mx[inc][i].rbegin()->first) S.update(i, mx[inc][i].rbegin()->first, 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))>>1;
            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)>>1;
            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))>>1;
            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)>>1;
            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))>>1;
            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))>>1;
            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)>>1;
            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))>>1;
            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)>>1;
            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))>>1;
            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 49 ms 117840 KB Output is correct
2 Correct 19 ms 117852 KB Output is correct
3 Correct 19 ms 117852 KB Output is correct
4 Correct 19 ms 117852 KB Output is correct
5 Correct 20 ms 117852 KB Output is correct
6 Correct 22 ms 117988 KB Output is correct
7 Correct 20 ms 117852 KB Output is correct
8 Correct 21 ms 117848 KB Output is correct
9 Correct 20 ms 117852 KB Output is correct
10 Correct 23 ms 118112 KB Output is correct
11 Correct 20 ms 117852 KB Output is correct
12 Correct 25 ms 117852 KB Output is correct
13 Correct 20 ms 117852 KB Output is correct
14 Correct 21 ms 117924 KB Output is correct
15 Correct 22 ms 118008 KB Output is correct
16 Correct 20 ms 117984 KB Output is correct
17 Correct 21 ms 117996 KB Output is correct
18 Correct 21 ms 117852 KB Output is correct
19 Correct 20 ms 117940 KB Output is correct
20 Correct 20 ms 117848 KB Output is correct
21 Correct 19 ms 117852 KB Output is correct
22 Correct 20 ms 117852 KB Output is correct
23 Correct 20 ms 117852 KB Output is correct
24 Correct 20 ms 117848 KB Output is correct
25 Correct 21 ms 117872 KB Output is correct
26 Correct 20 ms 117948 KB Output is correct
27 Correct 20 ms 117740 KB Output is correct
28 Correct 20 ms 117852 KB Output is correct
29 Correct 20 ms 117852 KB Output is correct
30 Correct 23 ms 117852 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117840 KB Output is correct
2 Correct 19 ms 117852 KB Output is correct
3 Correct 19 ms 117852 KB Output is correct
4 Correct 19 ms 117852 KB Output is correct
5 Correct 20 ms 117852 KB Output is correct
6 Correct 22 ms 117988 KB Output is correct
7 Correct 20 ms 117852 KB Output is correct
8 Correct 21 ms 117848 KB Output is correct
9 Correct 20 ms 117852 KB Output is correct
10 Correct 23 ms 118112 KB Output is correct
11 Correct 20 ms 117852 KB Output is correct
12 Correct 25 ms 117852 KB Output is correct
13 Correct 20 ms 117852 KB Output is correct
14 Correct 21 ms 117924 KB Output is correct
15 Correct 22 ms 118008 KB Output is correct
16 Correct 20 ms 117984 KB Output is correct
17 Correct 21 ms 117996 KB Output is correct
18 Correct 21 ms 117852 KB Output is correct
19 Correct 20 ms 117940 KB Output is correct
20 Correct 20 ms 117848 KB Output is correct
21 Correct 19 ms 117852 KB Output is correct
22 Correct 20 ms 117852 KB Output is correct
23 Correct 20 ms 117852 KB Output is correct
24 Correct 20 ms 117848 KB Output is correct
25 Correct 21 ms 117872 KB Output is correct
26 Correct 20 ms 117948 KB Output is correct
27 Correct 20 ms 117740 KB Output is correct
28 Correct 20 ms 117852 KB Output is correct
29 Correct 20 ms 117852 KB Output is correct
30 Correct 23 ms 117852 KB Output is correct
31 Correct 1042 ms 162940 KB Output is correct
32 Correct 71 ms 122316 KB Output is correct
33 Correct 983 ms 157372 KB Output is correct
34 Correct 1038 ms 155916 KB Output is correct
35 Correct 1084 ms 165136 KB Output is correct
36 Correct 1037 ms 164724 KB Output is correct
37 Correct 670 ms 156348 KB Output is correct
38 Correct 659 ms 156536 KB Output is correct
39 Correct 546 ms 154228 KB Output is correct
40 Correct 568 ms 155072 KB Output is correct
41 Correct 489 ms 139964 KB Output is correct
42 Correct 466 ms 139764 KB Output is correct
43 Correct 69 ms 123852 KB Output is correct
44 Correct 470 ms 139184 KB Output is correct
45 Correct 507 ms 139196 KB Output is correct
46 Correct 482 ms 139196 KB Output is correct
47 Correct 272 ms 135124 KB Output is correct
48 Correct 274 ms 137664 KB Output is correct
49 Correct 318 ms 137876 KB Output is correct
50 Correct 328 ms 137148 KB Output is correct
51 Correct 328 ms 138176 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2763 ms 244228 KB Output is correct
2 Correct 1563 ms 248548 KB Output is correct
3 Correct 680 ms 221716 KB Output is correct
4 Correct 2485 ms 241100 KB Output is correct
5 Correct 1523 ms 247124 KB Output is correct
6 Correct 1554 ms 247244 KB Output is correct
7 Correct 644 ms 221900 KB Output is correct
8 Correct 2555 ms 241676 KB Output is correct
9 Correct 2868 ms 247476 KB Output is correct
10 Correct 2031 ms 248164 KB Output is correct
11 Correct 1454 ms 246408 KB Output is correct
12 Correct 1676 ms 248028 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3708 ms 541720 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117840 KB Output is correct
2 Correct 19 ms 117852 KB Output is correct
3 Correct 19 ms 117852 KB Output is correct
4 Correct 19 ms 117852 KB Output is correct
5 Correct 20 ms 117852 KB Output is correct
6 Correct 22 ms 117988 KB Output is correct
7 Correct 20 ms 117852 KB Output is correct
8 Correct 21 ms 117848 KB Output is correct
9 Correct 20 ms 117852 KB Output is correct
10 Correct 23 ms 118112 KB Output is correct
11 Correct 20 ms 117852 KB Output is correct
12 Correct 25 ms 117852 KB Output is correct
13 Correct 20 ms 117852 KB Output is correct
14 Correct 21 ms 117924 KB Output is correct
15 Correct 22 ms 118008 KB Output is correct
16 Correct 20 ms 117984 KB Output is correct
17 Correct 21 ms 117996 KB Output is correct
18 Correct 21 ms 117852 KB Output is correct
19 Correct 20 ms 117940 KB Output is correct
20 Correct 20 ms 117848 KB Output is correct
21 Correct 19 ms 117852 KB Output is correct
22 Correct 20 ms 117852 KB Output is correct
23 Correct 20 ms 117852 KB Output is correct
24 Correct 20 ms 117848 KB Output is correct
25 Correct 21 ms 117872 KB Output is correct
26 Correct 20 ms 117948 KB Output is correct
27 Correct 20 ms 117740 KB Output is correct
28 Correct 20 ms 117852 KB Output is correct
29 Correct 20 ms 117852 KB Output is correct
30 Correct 23 ms 117852 KB Output is correct
31 Correct 1042 ms 162940 KB Output is correct
32 Correct 71 ms 122316 KB Output is correct
33 Correct 983 ms 157372 KB Output is correct
34 Correct 1038 ms 155916 KB Output is correct
35 Correct 1084 ms 165136 KB Output is correct
36 Correct 1037 ms 164724 KB Output is correct
37 Correct 670 ms 156348 KB Output is correct
38 Correct 659 ms 156536 KB Output is correct
39 Correct 546 ms 154228 KB Output is correct
40 Correct 568 ms 155072 KB Output is correct
41 Correct 489 ms 139964 KB Output is correct
42 Correct 466 ms 139764 KB Output is correct
43 Correct 69 ms 123852 KB Output is correct
44 Correct 470 ms 139184 KB Output is correct
45 Correct 507 ms 139196 KB Output is correct
46 Correct 482 ms 139196 KB Output is correct
47 Correct 272 ms 135124 KB Output is correct
48 Correct 274 ms 137664 KB Output is correct
49 Correct 318 ms 137876 KB Output is correct
50 Correct 328 ms 137148 KB Output is correct
51 Correct 328 ms 138176 KB Output is correct
52 Correct 162 ms 138436 KB Output is correct
53 Correct 145 ms 131880 KB Output is correct
54 Correct 544 ms 144180 KB Output is correct
55 Correct 376 ms 139052 KB Output is correct
56 Correct 310 ms 139200 KB Output is correct
57 Correct 482 ms 139140 KB Output is correct
58 Correct 405 ms 137180 KB Output is correct
59 Correct 348 ms 137148 KB Output is correct
60 Correct 441 ms 139080 KB Output is correct
61 Correct 77 ms 133432 KB Output is correct
62 Correct 173 ms 139556 KB Output is correct
63 Correct 373 ms 140584 KB Output is correct
64 Correct 436 ms 140980 KB Output is correct
65 Correct 504 ms 140484 KB Output is correct
66 Correct 486 ms 139112 KB Output is correct
67 Correct 138 ms 124608 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117840 KB Output is correct
2 Correct 19 ms 117852 KB Output is correct
3 Correct 19 ms 117852 KB Output is correct
4 Correct 19 ms 117852 KB Output is correct
5 Correct 20 ms 117852 KB Output is correct
6 Correct 22 ms 117988 KB Output is correct
7 Correct 20 ms 117852 KB Output is correct
8 Correct 21 ms 117848 KB Output is correct
9 Correct 20 ms 117852 KB Output is correct
10 Correct 23 ms 118112 KB Output is correct
11 Correct 20 ms 117852 KB Output is correct
12 Correct 25 ms 117852 KB Output is correct
13 Correct 20 ms 117852 KB Output is correct
14 Correct 21 ms 117924 KB Output is correct
15 Correct 22 ms 118008 KB Output is correct
16 Correct 20 ms 117984 KB Output is correct
17 Correct 21 ms 117996 KB Output is correct
18 Correct 21 ms 117852 KB Output is correct
19 Correct 20 ms 117940 KB Output is correct
20 Correct 20 ms 117848 KB Output is correct
21 Correct 19 ms 117852 KB Output is correct
22 Correct 20 ms 117852 KB Output is correct
23 Correct 20 ms 117852 KB Output is correct
24 Correct 20 ms 117848 KB Output is correct
25 Correct 21 ms 117872 KB Output is correct
26 Correct 20 ms 117948 KB Output is correct
27 Correct 20 ms 117740 KB Output is correct
28 Correct 20 ms 117852 KB Output is correct
29 Correct 20 ms 117852 KB Output is correct
30 Correct 23 ms 117852 KB Output is correct
31 Correct 1042 ms 162940 KB Output is correct
32 Correct 71 ms 122316 KB Output is correct
33 Correct 983 ms 157372 KB Output is correct
34 Correct 1038 ms 155916 KB Output is correct
35 Correct 1084 ms 165136 KB Output is correct
36 Correct 1037 ms 164724 KB Output is correct
37 Correct 670 ms 156348 KB Output is correct
38 Correct 659 ms 156536 KB Output is correct
39 Correct 546 ms 154228 KB Output is correct
40 Correct 568 ms 155072 KB Output is correct
41 Correct 489 ms 139964 KB Output is correct
42 Correct 466 ms 139764 KB Output is correct
43 Correct 69 ms 123852 KB Output is correct
44 Correct 470 ms 139184 KB Output is correct
45 Correct 507 ms 139196 KB Output is correct
46 Correct 482 ms 139196 KB Output is correct
47 Correct 272 ms 135124 KB Output is correct
48 Correct 274 ms 137664 KB Output is correct
49 Correct 318 ms 137876 KB Output is correct
50 Correct 328 ms 137148 KB Output is correct
51 Correct 328 ms 138176 KB Output is correct
52 Correct 2763 ms 244228 KB Output is correct
53 Correct 1563 ms 248548 KB Output is correct
54 Correct 680 ms 221716 KB Output is correct
55 Correct 2485 ms 241100 KB Output is correct
56 Correct 1523 ms 247124 KB Output is correct
57 Correct 1554 ms 247244 KB Output is correct
58 Correct 644 ms 221900 KB Output is correct
59 Correct 2555 ms 241676 KB Output is correct
60 Correct 2868 ms 247476 KB Output is correct
61 Correct 2031 ms 248164 KB Output is correct
62 Correct 1454 ms 246408 KB Output is correct
63 Correct 1676 ms 248028 KB Output is correct
64 Runtime error 3708 ms 541720 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -