oj.uz

Submission #979802

# Submission time Handle Problem Language Result Execution time Memory
979802 2024-05-11T11:44:39 Z Jarif_Rahman New Home (APIO18_new_home) C++17
80 / 100
 3838 ms 694804 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<<=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, N = 3e5;
tuple<int, int, int, int> queries[3*N];
multiset<int> stores[N];
unordered_map<int, multiset<int>> mx[2];
sparse_segtree S(L);
int cnt_t[N];
int nonzero = 0;
int ans[N];

void 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);
}
void 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);
};

void add(int t, int x){
    auto it = stores[t].insert(x);
    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);
    }
};
void remove(int t, int x){
    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);
};

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

    int n, k, q; cin >> n >> k >> q;
    mx[0].reserve(n+q);
    mx[1].reserve(n+q);

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

    fill(cnt_t, cnt_t+k, 0);
    for(int qq = 0; qq < 2*n+q; qq++){
        auto [_, type, x, i] = queries[qq];
        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 i = 0; i < q; i++) cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 182872 KB Output is correct
2 Correct 33 ms 182848 KB Output is correct
3 Correct 30 ms 182828 KB Output is correct
4 Correct 30 ms 182876 KB Output is correct
5 Correct 30 ms 182724 KB Output is correct
6 Correct 32 ms 182876 KB Output is correct
7 Correct 30 ms 182868 KB Output is correct
8 Correct 34 ms 182876 KB Output is correct
9 Correct 32 ms 182936 KB Output is correct
10 Correct 32 ms 183132 KB Output is correct
11 Correct 32 ms 182868 KB Output is correct
12 Correct 32 ms 182876 KB Output is correct
13 Correct 30 ms 182700 KB Output is correct
14 Correct 31 ms 182732 KB Output is correct
15 Correct 31 ms 182868 KB Output is correct
16 Correct 31 ms 182872 KB Output is correct
17 Correct 32 ms 182860 KB Output is correct
18 Correct 32 ms 182876 KB Output is correct
19 Correct 31 ms 182928 KB Output is correct
20 Correct 31 ms 182872 KB Output is correct
21 Correct 30 ms 182740 KB Output is correct
22 Correct 31 ms 182916 KB Output is correct
23 Correct 31 ms 182868 KB Output is correct
24 Correct 31 ms 182868 KB Output is correct
25 Correct 32 ms 182864 KB Output is correct
26 Correct 31 ms 182864 KB Output is correct
27 Correct 30 ms 182864 KB Output is correct
28 Correct 32 ms 182876 KB Output is correct
29 Correct 30 ms 182868 KB Output is correct
30 Correct 31 ms 182868 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 182872 KB Output is correct
2 Correct 33 ms 182848 KB Output is correct
3 Correct 30 ms 182828 KB Output is correct
4 Correct 30 ms 182876 KB Output is correct
5 Correct 30 ms 182724 KB Output is correct
6 Correct 32 ms 182876 KB Output is correct
7 Correct 30 ms 182868 KB Output is correct
8 Correct 34 ms 182876 KB Output is correct
9 Correct 32 ms 182936 KB Output is correct
10 Correct 32 ms 183132 KB Output is correct
11 Correct 32 ms 182868 KB Output is correct
12 Correct 32 ms 182876 KB Output is correct
13 Correct 30 ms 182700 KB Output is correct
14 Correct 31 ms 182732 KB Output is correct
15 Correct 31 ms 182868 KB Output is correct
16 Correct 31 ms 182872 KB Output is correct
17 Correct 32 ms 182860 KB Output is correct
18 Correct 32 ms 182876 KB Output is correct
19 Correct 31 ms 182928 KB Output is correct
20 Correct 31 ms 182872 KB Output is correct
21 Correct 30 ms 182740 KB Output is correct
22 Correct 31 ms 182916 KB Output is correct
23 Correct 31 ms 182868 KB Output is correct
24 Correct 31 ms 182868 KB Output is correct
25 Correct 32 ms 182864 KB Output is correct
26 Correct 31 ms 182864 KB Output is correct
27 Correct 30 ms 182864 KB Output is correct
28 Correct 32 ms 182876 KB Output is correct
29 Correct 30 ms 182868 KB Output is correct
30 Correct 31 ms 182868 KB Output is correct
31 Correct 768 ms 220856 KB Output is correct
32 Correct 116 ms 191532 KB Output is correct
33 Correct 723 ms 219192 KB Output is correct
34 Correct 662 ms 217728 KB Output is correct
35 Correct 809 ms 221908 KB Output is correct
36 Correct 749 ms 221776 KB Output is correct
37 Correct 467 ms 217856 KB Output is correct
38 Correct 475 ms 218220 KB Output is correct
39 Correct 397 ms 216384 KB Output is correct
40 Correct 457 ms 217252 KB Output is correct
41 Correct 270 ms 202320 KB Output is correct
42 Correct 253 ms 201776 KB Output is correct
43 Correct 110 ms 195112 KB Output is correct
44 Correct 281 ms 202044 KB Output is correct
45 Correct 252 ms 202068 KB Output is correct
46 Correct 248 ms 202320 KB Output is correct
47 Correct 168 ms 198736 KB Output is correct
48 Correct 179 ms 199764 KB Output is correct
49 Correct 201 ms 201040 KB Output is correct
50 Correct 203 ms 200276 KB Output is correct
51 Correct 207 ms 201516 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1805 ms 287256 KB Output is correct
2 Correct 1163 ms 295540 KB Output is correct
3 Correct 566 ms 249724 KB Output is correct
4 Correct 1663 ms 281236 KB Output is correct
5 Correct 1188 ms 294908 KB Output is correct
6 Correct 1159 ms 295580 KB Output is correct
7 Correct 550 ms 249684 KB Output is correct
8 Correct 1620 ms 281072 KB Output is correct
9 Correct 1893 ms 291916 KB Output is correct
10 Correct 1359 ms 296032 KB Output is correct
11 Correct 1061 ms 293936 KB Output is correct
12 Correct 1219 ms 295728 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3314 ms 312160 KB Output is correct
2 Correct 491 ms 234156 KB Output is correct
3 Correct 3151 ms 318824 KB Output is correct
4 Correct 713 ms 261500 KB Output is correct
5 Correct 2376 ms 302244 KB Output is correct
6 Correct 2133 ms 293408 KB Output is correct
7 Correct 2935 ms 330648 KB Output is correct
8 Correct 3079 ms 331448 KB Output is correct
9 Correct 727 ms 262816 KB Output is correct
10 Correct 2401 ms 301596 KB Output is correct
11 Correct 3157 ms 319648 KB Output is correct
12 Correct 3423 ms 331856 KB Output is correct
13 Correct 1521 ms 320736 KB Output is correct
14 Correct 1532 ms 321492 KB Output is correct
15 Correct 1727 ms 326840 KB Output is correct
16 Correct 2040 ms 326664 KB Output is correct
17 Correct 1883 ms 327636 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 182872 KB Output is correct
2 Correct 33 ms 182848 KB Output is correct
3 Correct 30 ms 182828 KB Output is correct
4 Correct 30 ms 182876 KB Output is correct
5 Correct 30 ms 182724 KB Output is correct
6 Correct 32 ms 182876 KB Output is correct
7 Correct 30 ms 182868 KB Output is correct
8 Correct 34 ms 182876 KB Output is correct
9 Correct 32 ms 182936 KB Output is correct
10 Correct 32 ms 183132 KB Output is correct
11 Correct 32 ms 182868 KB Output is correct
12 Correct 32 ms 182876 KB Output is correct
13 Correct 30 ms 182700 KB Output is correct
14 Correct 31 ms 182732 KB Output is correct
15 Correct 31 ms 182868 KB Output is correct
16 Correct 31 ms 182872 KB Output is correct
17 Correct 32 ms 182860 KB Output is correct
18 Correct 32 ms 182876 KB Output is correct
19 Correct 31 ms 182928 KB Output is correct
20 Correct 31 ms 182872 KB Output is correct
21 Correct 30 ms 182740 KB Output is correct
22 Correct 31 ms 182916 KB Output is correct
23 Correct 31 ms 182868 KB Output is correct
24 Correct 31 ms 182868 KB Output is correct
25 Correct 32 ms 182864 KB Output is correct
26 Correct 31 ms 182864 KB Output is correct
27 Correct 30 ms 182864 KB Output is correct
28 Correct 32 ms 182876 KB Output is correct
29 Correct 30 ms 182868 KB Output is correct
30 Correct 31 ms 182868 KB Output is correct
31 Correct 768 ms 220856 KB Output is correct
32 Correct 116 ms 191532 KB Output is correct
33 Correct 723 ms 219192 KB Output is correct
34 Correct 662 ms 217728 KB Output is correct
35 Correct 809 ms 221908 KB Output is correct
36 Correct 749 ms 221776 KB Output is correct
37 Correct 467 ms 217856 KB Output is correct
38 Correct 475 ms 218220 KB Output is correct
39 Correct 397 ms 216384 KB Output is correct
40 Correct 457 ms 217252 KB Output is correct
41 Correct 270 ms 202320 KB Output is correct
42 Correct 253 ms 201776 KB Output is correct
43 Correct 110 ms 195112 KB Output is correct
44 Correct 281 ms 202044 KB Output is correct
45 Correct 252 ms 202068 KB Output is correct
46 Correct 248 ms 202320 KB Output is correct
47 Correct 168 ms 198736 KB Output is correct
48 Correct 179 ms 199764 KB Output is correct
49 Correct 201 ms 201040 KB Output is correct
50 Correct 203 ms 200276 KB Output is correct
51 Correct 207 ms 201516 KB Output is correct
52 Correct 126 ms 197676 KB Output is correct
53 Correct 120 ms 192200 KB Output is correct
54 Correct 343 ms 206016 KB Output is correct
55 Correct 228 ms 200788 KB Output is correct
56 Correct 202 ms 200112 KB Output is correct
57 Correct 256 ms 201724 KB Output is correct
58 Correct 232 ms 199280 KB Output is correct
59 Correct 221 ms 198944 KB Output is correct
60 Correct 250 ms 201112 KB Output is correct
61 Correct 104 ms 197928 KB Output is correct
62 Correct 128 ms 197716 KB Output is correct
63 Correct 248 ms 201808 KB Output is correct
64 Correct 286 ms 202132 KB Output is correct
65 Correct 317 ms 202240 KB Output is correct
66 Correct 279 ms 202032 KB Output is correct
67 Correct 153 ms 191056 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 182872 KB Output is correct
2 Correct 33 ms 182848 KB Output is correct
3 Correct 30 ms 182828 KB Output is correct
4 Correct 30 ms 182876 KB Output is correct
5 Correct 30 ms 182724 KB Output is correct
6 Correct 32 ms 182876 KB Output is correct
7 Correct 30 ms 182868 KB Output is correct
8 Correct 34 ms 182876 KB Output is correct
9 Correct 32 ms 182936 KB Output is correct
10 Correct 32 ms 183132 KB Output is correct
11 Correct 32 ms 182868 KB Output is correct
12 Correct 32 ms 182876 KB Output is correct
13 Correct 30 ms 182700 KB Output is correct
14 Correct 31 ms 182732 KB Output is correct
15 Correct 31 ms 182868 KB Output is correct
16 Correct 31 ms 182872 KB Output is correct
17 Correct 32 ms 182860 KB Output is correct
18 Correct 32 ms 182876 KB Output is correct
19 Correct 31 ms 182928 KB Output is correct
20 Correct 31 ms 182872 KB Output is correct
21 Correct 30 ms 182740 KB Output is correct
22 Correct 31 ms 182916 KB Output is correct
23 Correct 31 ms 182868 KB Output is correct
24 Correct 31 ms 182868 KB Output is correct
25 Correct 32 ms 182864 KB Output is correct
26 Correct 31 ms 182864 KB Output is correct
27 Correct 30 ms 182864 KB Output is correct
28 Correct 32 ms 182876 KB Output is correct
29 Correct 30 ms 182868 KB Output is correct
30 Correct 31 ms 182868 KB Output is correct
31 Correct 768 ms 220856 KB Output is correct
32 Correct 116 ms 191532 KB Output is correct
33 Correct 723 ms 219192 KB Output is correct
34 Correct 662 ms 217728 KB Output is correct
35 Correct 809 ms 221908 KB Output is correct
36 Correct 749 ms 221776 KB Output is correct
37 Correct 467 ms 217856 KB Output is correct
38 Correct 475 ms 218220 KB Output is correct
39 Correct 397 ms 216384 KB Output is correct
40 Correct 457 ms 217252 KB Output is correct
41 Correct 270 ms 202320 KB Output is correct
42 Correct 253 ms 201776 KB Output is correct
43 Correct 110 ms 195112 KB Output is correct
44 Correct 281 ms 202044 KB Output is correct
45 Correct 252 ms 202068 KB Output is correct
46 Correct 248 ms 202320 KB Output is correct
47 Correct 168 ms 198736 KB Output is correct
48 Correct 179 ms 199764 KB Output is correct
49 Correct 201 ms 201040 KB Output is correct
50 Correct 203 ms 200276 KB Output is correct
51 Correct 207 ms 201516 KB Output is correct
52 Correct 1805 ms 287256 KB Output is correct
53 Correct 1163 ms 295540 KB Output is correct
54 Correct 566 ms 249724 KB Output is correct
55 Correct 1663 ms 281236 KB Output is correct
56 Correct 1188 ms 294908 KB Output is correct
57 Correct 1159 ms 295580 KB Output is correct
58 Correct 550 ms 249684 KB Output is correct
59 Correct 1620 ms 281072 KB Output is correct
60 Correct 1893 ms 291916 KB Output is correct
61 Correct 1359 ms 296032 KB Output is correct
62 Correct 1061 ms 293936 KB Output is correct
63 Correct 1219 ms 295728 KB Output is correct
64 Correct 3314 ms 312160 KB Output is correct
65 Correct 491 ms 234156 KB Output is correct
66 Correct 3151 ms 318824 KB Output is correct
67 Correct 713 ms 261500 KB Output is correct
68 Correct 2376 ms 302244 KB Output is correct
69 Correct 2133 ms 293408 KB Output is correct
70 Correct 2935 ms 330648 KB Output is correct
71 Correct 3079 ms 331448 KB Output is correct
72 Correct 727 ms 262816 KB Output is correct
73 Correct 2401 ms 301596 KB Output is correct
74 Correct 3157 ms 319648 KB Output is correct
75 Correct 3423 ms 331856 KB Output is correct
76 Correct 1521 ms 320736 KB Output is correct
77 Correct 1532 ms 321492 KB Output is correct
78 Correct 1727 ms 326840 KB Output is correct
79 Correct 2040 ms 326664 KB Output is correct
80 Correct 1883 ms 327636 KB Output is correct
81 Correct 126 ms 197676 KB Output is correct
82 Correct 120 ms 192200 KB Output is correct
83 Correct 343 ms 206016 KB Output is correct
84 Correct 228 ms 200788 KB Output is correct
85 Correct 202 ms 200112 KB Output is correct
86 Correct 256 ms 201724 KB Output is correct
87 Correct 232 ms 199280 KB Output is correct
88 Correct 221 ms 198944 KB Output is correct
89 Correct 250 ms 201112 KB Output is correct
90 Correct 104 ms 197928 KB Output is correct
91 Correct 128 ms 197716 KB Output is correct
92 Correct 248 ms 201808 KB Output is correct
93 Correct 286 ms 202132 KB Output is correct
94 Correct 317 ms 202240 KB Output is correct
95 Correct 279 ms 202032 KB Output is correct
96 Correct 153 ms 191056 KB Output is correct
97 Correct 851 ms 263564 KB Output is correct
98 Correct 485 ms 221780 KB Output is correct
99 Runtime error 3838 ms 694804 KB Execution killed with signal 7
100 Halted 0 ms 0 KB -