oj.uz

Submission #979801

# Submission time Handle Problem Language Result Execution time Memory
979801 2024-05-11T11:43:30 Z Jarif_Rahman New Home (APIO18_new_home) C++17
57 / 100
 3345 ms 603480 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 = 6e6;

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 78 ms 159312 KB Output is correct
2 Correct 29 ms 159396 KB Output is correct
3 Correct 29 ms 159592 KB Output is correct
4 Correct 27 ms 159248 KB Output is correct
5 Correct 26 ms 159324 KB Output is correct
6 Correct 28 ms 159580 KB Output is correct
7 Correct 27 ms 159404 KB Output is correct
8 Correct 29 ms 159328 KB Output is correct
9 Correct 26 ms 159364 KB Output is correct
10 Correct 28 ms 159480 KB Output is correct
11 Correct 31 ms 159312 KB Output is correct
12 Correct 28 ms 159324 KB Output is correct
13 Correct 28 ms 159412 KB Output is correct
14 Correct 27 ms 159316 KB Output is correct
15 Correct 27 ms 159324 KB Output is correct
16 Correct 27 ms 159316 KB Output is correct
17 Correct 27 ms 159360 KB Output is correct
18 Correct 28 ms 159336 KB Output is correct
19 Correct 27 ms 159316 KB Output is correct
20 Correct 28 ms 159324 KB Output is correct
21 Correct 27 ms 159316 KB Output is correct
22 Correct 27 ms 159548 KB Output is correct
23 Correct 26 ms 159324 KB Output is correct
24 Correct 27 ms 159348 KB Output is correct
25 Correct 26 ms 159324 KB Output is correct
26 Correct 27 ms 159312 KB Output is correct
27 Correct 27 ms 159316 KB Output is correct
28 Correct 27 ms 159312 KB Output is correct
29 Correct 30 ms 159428 KB Output is correct
30 Correct 28 ms 159324 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 159312 KB Output is correct
2 Correct 29 ms 159396 KB Output is correct
3 Correct 29 ms 159592 KB Output is correct
4 Correct 27 ms 159248 KB Output is correct
5 Correct 26 ms 159324 KB Output is correct
6 Correct 28 ms 159580 KB Output is correct
7 Correct 27 ms 159404 KB Output is correct
8 Correct 29 ms 159328 KB Output is correct
9 Correct 26 ms 159364 KB Output is correct
10 Correct 28 ms 159480 KB Output is correct
11 Correct 31 ms 159312 KB Output is correct
12 Correct 28 ms 159324 KB Output is correct
13 Correct 28 ms 159412 KB Output is correct
14 Correct 27 ms 159316 KB Output is correct
15 Correct 27 ms 159324 KB Output is correct
16 Correct 27 ms 159316 KB Output is correct
17 Correct 27 ms 159360 KB Output is correct
18 Correct 28 ms 159336 KB Output is correct
19 Correct 27 ms 159316 KB Output is correct
20 Correct 28 ms 159324 KB Output is correct
21 Correct 27 ms 159316 KB Output is correct
22 Correct 27 ms 159548 KB Output is correct
23 Correct 26 ms 159324 KB Output is correct
24 Correct 27 ms 159348 KB Output is correct
25 Correct 26 ms 159324 KB Output is correct
26 Correct 27 ms 159312 KB Output is correct
27 Correct 27 ms 159316 KB Output is correct
28 Correct 27 ms 159312 KB Output is correct
29 Correct 30 ms 159428 KB Output is correct
30 Correct 28 ms 159324 KB Output is correct
31 Correct 760 ms 197448 KB Output is correct
32 Correct 117 ms 168424 KB Output is correct
33 Correct 705 ms 195676 KB Output is correct
34 Correct 653 ms 194324 KB Output is correct
35 Correct 767 ms 198200 KB Output is correct
36 Correct 779 ms 198380 KB Output is correct
37 Correct 496 ms 194452 KB Output is correct
38 Correct 490 ms 194712 KB Output is correct
39 Correct 381 ms 192916 KB Output is correct
40 Correct 425 ms 193992 KB Output is correct
41 Correct 255 ms 178516 KB Output is correct
42 Correct 246 ms 178308 KB Output is correct
43 Correct 107 ms 171640 KB Output is correct
44 Correct 259 ms 178512 KB Output is correct
45 Correct 245 ms 178552 KB Output is correct
46 Correct 242 ms 178520 KB Output is correct
47 Correct 166 ms 175196 KB Output is correct
48 Correct 182 ms 176212 KB Output is correct
49 Correct 192 ms 177524 KB Output is correct
50 Correct 200 ms 176764 KB Output is correct
51 Correct 206 ms 178092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1829 ms 263708 KB Output is correct
2 Correct 1218 ms 272156 KB Output is correct
3 Correct 571 ms 226304 KB Output is correct
4 Correct 1614 ms 257524 KB Output is correct
5 Correct 1176 ms 271508 KB Output is correct
6 Correct 1152 ms 271840 KB Output is correct
7 Correct 547 ms 226388 KB Output is correct
8 Correct 1626 ms 257572 KB Output is correct
9 Correct 1902 ms 268444 KB Output is correct
10 Correct 1377 ms 272572 KB Output is correct
11 Correct 1067 ms 270300 KB Output is correct
12 Correct 1237 ms 271972 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3345 ms 288924 KB Output is correct
2 Correct 487 ms 214680 KB Output is correct
3 Runtime error 3077 ms 603480 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 159312 KB Output is correct
2 Correct 29 ms 159396 KB Output is correct
3 Correct 29 ms 159592 KB Output is correct
4 Correct 27 ms 159248 KB Output is correct
5 Correct 26 ms 159324 KB Output is correct
6 Correct 28 ms 159580 KB Output is correct
7 Correct 27 ms 159404 KB Output is correct
8 Correct 29 ms 159328 KB Output is correct
9 Correct 26 ms 159364 KB Output is correct
10 Correct 28 ms 159480 KB Output is correct
11 Correct 31 ms 159312 KB Output is correct
12 Correct 28 ms 159324 KB Output is correct
13 Correct 28 ms 159412 KB Output is correct
14 Correct 27 ms 159316 KB Output is correct
15 Correct 27 ms 159324 KB Output is correct
16 Correct 27 ms 159316 KB Output is correct
17 Correct 27 ms 159360 KB Output is correct
18 Correct 28 ms 159336 KB Output is correct
19 Correct 27 ms 159316 KB Output is correct
20 Correct 28 ms 159324 KB Output is correct
21 Correct 27 ms 159316 KB Output is correct
22 Correct 27 ms 159548 KB Output is correct
23 Correct 26 ms 159324 KB Output is correct
24 Correct 27 ms 159348 KB Output is correct
25 Correct 26 ms 159324 KB Output is correct
26 Correct 27 ms 159312 KB Output is correct
27 Correct 27 ms 159316 KB Output is correct
28 Correct 27 ms 159312 KB Output is correct
29 Correct 30 ms 159428 KB Output is correct
30 Correct 28 ms 159324 KB Output is correct
31 Correct 760 ms 197448 KB Output is correct
32 Correct 117 ms 168424 KB Output is correct
33 Correct 705 ms 195676 KB Output is correct
34 Correct 653 ms 194324 KB Output is correct
35 Correct 767 ms 198200 KB Output is correct
36 Correct 779 ms 198380 KB Output is correct
37 Correct 496 ms 194452 KB Output is correct
38 Correct 490 ms 194712 KB Output is correct
39 Correct 381 ms 192916 KB Output is correct
40 Correct 425 ms 193992 KB Output is correct
41 Correct 255 ms 178516 KB Output is correct
42 Correct 246 ms 178308 KB Output is correct
43 Correct 107 ms 171640 KB Output is correct
44 Correct 259 ms 178512 KB Output is correct
45 Correct 245 ms 178552 KB Output is correct
46 Correct 242 ms 178520 KB Output is correct
47 Correct 166 ms 175196 KB Output is correct
48 Correct 182 ms 176212 KB Output is correct
49 Correct 192 ms 177524 KB Output is correct
50 Correct 200 ms 176764 KB Output is correct
51 Correct 206 ms 178092 KB Output is correct
52 Correct 123 ms 174100 KB Output is correct
53 Correct 123 ms 168804 KB Output is correct
54 Correct 320 ms 182352 KB Output is correct
55 Correct 223 ms 177352 KB Output is correct
56 Correct 204 ms 176468 KB Output is correct
57 Correct 251 ms 178028 KB Output is correct
58 Correct 234 ms 175736 KB Output is correct
59 Correct 211 ms 175292 KB Output is correct
60 Correct 247 ms 177548 KB Output is correct
61 Correct 99 ms 174420 KB Output is correct
62 Correct 120 ms 174160 KB Output is correct
63 Correct 317 ms 178092 KB Output is correct
64 Correct 283 ms 178772 KB Output is correct
65 Correct 302 ms 178516 KB Output is correct
66 Correct 263 ms 178652 KB Output is correct
67 Correct 153 ms 167508 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 159312 KB Output is correct
2 Correct 29 ms 159396 KB Output is correct
3 Correct 29 ms 159592 KB Output is correct
4 Correct 27 ms 159248 KB Output is correct
5 Correct 26 ms 159324 KB Output is correct
6 Correct 28 ms 159580 KB Output is correct
7 Correct 27 ms 159404 KB Output is correct
8 Correct 29 ms 159328 KB Output is correct
9 Correct 26 ms 159364 KB Output is correct
10 Correct 28 ms 159480 KB Output is correct
11 Correct 31 ms 159312 KB Output is correct
12 Correct 28 ms 159324 KB Output is correct
13 Correct 28 ms 159412 KB Output is correct
14 Correct 27 ms 159316 KB Output is correct
15 Correct 27 ms 159324 KB Output is correct
16 Correct 27 ms 159316 KB Output is correct
17 Correct 27 ms 159360 KB Output is correct
18 Correct 28 ms 159336 KB Output is correct
19 Correct 27 ms 159316 KB Output is correct
20 Correct 28 ms 159324 KB Output is correct
21 Correct 27 ms 159316 KB Output is correct
22 Correct 27 ms 159548 KB Output is correct
23 Correct 26 ms 159324 KB Output is correct
24 Correct 27 ms 159348 KB Output is correct
25 Correct 26 ms 159324 KB Output is correct
26 Correct 27 ms 159312 KB Output is correct
27 Correct 27 ms 159316 KB Output is correct
28 Correct 27 ms 159312 KB Output is correct
29 Correct 30 ms 159428 KB Output is correct
30 Correct 28 ms 159324 KB Output is correct
31 Correct 760 ms 197448 KB Output is correct
32 Correct 117 ms 168424 KB Output is correct
33 Correct 705 ms 195676 KB Output is correct
34 Correct 653 ms 194324 KB Output is correct
35 Correct 767 ms 198200 KB Output is correct
36 Correct 779 ms 198380 KB Output is correct
37 Correct 496 ms 194452 KB Output is correct
38 Correct 490 ms 194712 KB Output is correct
39 Correct 381 ms 192916 KB Output is correct
40 Correct 425 ms 193992 KB Output is correct
41 Correct 255 ms 178516 KB Output is correct
42 Correct 246 ms 178308 KB Output is correct
43 Correct 107 ms 171640 KB Output is correct
44 Correct 259 ms 178512 KB Output is correct
45 Correct 245 ms 178552 KB Output is correct
46 Correct 242 ms 178520 KB Output is correct
47 Correct 166 ms 175196 KB Output is correct
48 Correct 182 ms 176212 KB Output is correct
49 Correct 192 ms 177524 KB Output is correct
50 Correct 200 ms 176764 KB Output is correct
51 Correct 206 ms 178092 KB Output is correct
52 Correct 1829 ms 263708 KB Output is correct
53 Correct 1218 ms 272156 KB Output is correct
54 Correct 571 ms 226304 KB Output is correct
55 Correct 1614 ms 257524 KB Output is correct
56 Correct 1176 ms 271508 KB Output is correct
57 Correct 1152 ms 271840 KB Output is correct
58 Correct 547 ms 226388 KB Output is correct
59 Correct 1626 ms 257572 KB Output is correct
60 Correct 1902 ms 268444 KB Output is correct
61 Correct 1377 ms 272572 KB Output is correct
62 Correct 1067 ms 270300 KB Output is correct
63 Correct 1237 ms 271972 KB Output is correct
64 Correct 3345 ms 288924 KB Output is correct
65 Correct 487 ms 214680 KB Output is correct
66 Runtime error 3077 ms 603480 KB Execution killed with signal 11
67 Halted 0 ms 0 KB -