Submission #979387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
979387	2024-05-10T18:44:37 Z	Jarif_Rahman	New Home (APIO18_new_home)	C++17	47 / 100	5000 ms	1048576 KB

new_home

#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{
    map<int, int> inc, dec;
    Node *l = nullptr, *r = nullptr;
    Node(){}
    Node(Node *_l, Node *_r): l(_l), r(_r){}
}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 add(int l, int r, Node* nd, int a, int b, ll x, bool inc){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            if(inc) nd->inc[x+a-l]++;
            else nd->dec[x-a+l]++;
            return;
        }
        int m = (a+b)/2;
        if(!nd->l) nd->l = newNode();
        if(!nd->r) nd->r = newNode();
        add(l, r, nd->l, a, m, x, inc);
        add(l, r, nd->r, m+1, b, x, inc);
    }
    void add(int l, int r, int x, bool inc){
        add(l, r, root, 0, n-1, x, inc);
    }
    void remove(int l, int r, Node* nd, int a, int b, int x, bool inc){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            if(inc){
                nd->inc[x+a-l]--;
                if(nd->inc[x+a-l] == 0) nd->inc.erase(x+a-l);
            }
            else{
                nd->dec[x-a+l]--;
                if(nd->dec[x-a+l] == 0) nd->dec.erase(x-a+l);
            }
            return;
        }
        int m = (a+b)/2;
        if(!nd->l) nd->l = new Node();
        if(!nd->r) nd->r = new Node();
        remove(l, r, nd->l, a, m, x, inc);
        remove(l, r, nd->r, m+1, b, x, inc);
    }
    void remove(int l, int r, int x, bool inc){
        remove(l, r, root, 0, n-1, x, inc);
    }

    int get(int i){
        Node* nd = root;
        int a = 0, b = n-1;
        int mx = 0;
        while(nd){
            if(!nd->inc.empty()) mx = max(mx, nd->inc.rbegin()->first+i-a);
            if(!nd->dec.empty()) mx = max(mx, nd->dec.rbegin()->first-i+a);
            int m = (a+b)/2;
            if(i <= m) nd = nd->l, b = m;
            else nd = nd->r, a = m+1;
        }
        return mx;
    }
};

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);
    sparse_segtree S(L);

    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){
            S.add(0, x, x, false);
            S.add(x+1, L-1, 1, true);
        }
        else if(it == stores[t].begin()){
            S.remove(0, *next(it), *next(it), false);
            S.add(0, x, x, false);
            int md = (x+*next(it))/2;
            if(md > x) S.add(x+1, md, 1, true);
            S.add(md+1, *next(it), *next(it)-md-1, false);
        }
        else if(next(it) == stores[t].end()){
            S.remove(*prev(it)+1, L-1, 1, true);
            int md = (*prev(it)+x)/2;
            if(md > *prev(it)) S.add(*prev(it)+1, md, 1, true);
            S.add(md+1, x, x-md-1, false);
            S.add(x+1, L-1, 1, true);
        }
        else{
            int md = (*prev(it)+*next(it))/2;
            if(md > *prev(it)) S.remove(*prev(it)+1, md, 1, true);
            S.remove(md+1, *next(it), *next(it)-md-1, false);

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

            md = (x+*next(it))/2;
            if(md > x) S.add(x+1, md, 1, true);
            S.add(md+1, *next(it), *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){
            S.remove(0, x, x, false);
            S.remove(x+1, L-1, 1, true);
        }
        else if(it == stores[t].begin()){
            S.add(0, *next(it), *next(it), false);
            S.remove(0, x, x, false);
            int md = (x+*next(it))/2;
            if(md > x) S.remove(x+1, md, 1, true);
            S.remove(md+1, *next(it), *next(it)-md-1, false);
        }
        else if(next(it) == stores[t].end()){
            S.add(*prev(it)+1, L-1, 1, true);
            int md = (*prev(it)+x)/2;
            if(md > *prev(it)) S.remove(*prev(it)+1, md, 1, true);
            S.remove(md+1, x, x-md-1, false);
            S.remove(x+1, L-1, 1, true);
        }
        else{
            int md = (*prev(it)+*next(it))/2;
            if(md > *prev(it)) S.add(*prev(it)+1, md, 1, true);
            S.add(md+1, *next(it), *next(it)-md-1, false);

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

            md = (x+*next(it))/2;
            if(md > x) S.remove(x+1, md, 1, true);
            S.remove(md+1, *next(it), *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] = S.get(x);
        }
    }

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

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	548176 KB	Output is correct
2	Correct	108 ms	548204 KB	Output is correct
3	Correct	109 ms	548380 KB	Output is correct
4	Correct	109 ms	548428 KB	Output is correct
5	Correct	110 ms	548288 KB	Output is correct
6	Correct	114 ms	548748 KB	Output is correct
7	Correct	111 ms	548688 KB	Output is correct
8	Correct	116 ms	549204 KB	Output is correct
9	Correct	112 ms	549020 KB	Output is correct
10	Correct	114 ms	549152 KB	Output is correct
11	Correct	113 ms	548756 KB	Output is correct
12	Correct	114 ms	548688 KB	Output is correct
13	Correct	111 ms	548432 KB	Output is correct
14	Correct	110 ms	548444 KB	Output is correct
15	Correct	115 ms	548916 KB	Output is correct
16	Correct	113 ms	548832 KB	Output is correct
17	Correct	118 ms	548424 KB	Output is correct
18	Correct	113 ms	548612 KB	Output is correct
19	Correct	117 ms	548972 KB	Output is correct
20	Correct	113 ms	548508 KB	Output is correct
21	Correct	110 ms	548432 KB	Output is correct
22	Correct	114 ms	549132 KB	Output is correct
23	Correct	117 ms	549056 KB	Output is correct
24	Correct	114 ms	549000 KB	Output is correct
25	Correct	115 ms	548436 KB	Output is correct
26	Correct	114 ms	548288 KB	Output is correct
27	Correct	115 ms	548688 KB	Output is correct
28	Correct	119 ms	548436 KB	Output is correct
29	Correct	113 ms	548436 KB	Output is correct
30	Correct	112 ms	548432 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	548176 KB	Output is correct
2	Correct	108 ms	548204 KB	Output is correct
3	Correct	109 ms	548380 KB	Output is correct
4	Correct	109 ms	548428 KB	Output is correct
5	Correct	110 ms	548288 KB	Output is correct
6	Correct	114 ms	548748 KB	Output is correct
7	Correct	111 ms	548688 KB	Output is correct
8	Correct	116 ms	549204 KB	Output is correct
9	Correct	112 ms	549020 KB	Output is correct
10	Correct	114 ms	549152 KB	Output is correct
11	Correct	113 ms	548756 KB	Output is correct
12	Correct	114 ms	548688 KB	Output is correct
13	Correct	111 ms	548432 KB	Output is correct
14	Correct	110 ms	548444 KB	Output is correct
15	Correct	115 ms	548916 KB	Output is correct
16	Correct	113 ms	548832 KB	Output is correct
17	Correct	118 ms	548424 KB	Output is correct
18	Correct	113 ms	548612 KB	Output is correct
19	Correct	117 ms	548972 KB	Output is correct
20	Correct	113 ms	548508 KB	Output is correct
21	Correct	110 ms	548432 KB	Output is correct
22	Correct	114 ms	549132 KB	Output is correct
23	Correct	117 ms	549056 KB	Output is correct
24	Correct	114 ms	549000 KB	Output is correct
25	Correct	115 ms	548436 KB	Output is correct
26	Correct	114 ms	548288 KB	Output is correct
27	Correct	115 ms	548688 KB	Output is correct
28	Correct	119 ms	548436 KB	Output is correct
29	Correct	113 ms	548436 KB	Output is correct
30	Correct	112 ms	548432 KB	Output is correct
31	Correct	3249 ms	658752 KB	Output is correct
32	Correct	154 ms	554700 KB	Output is correct
33	Correct	1902 ms	586364 KB	Output is correct
34	Correct	3164 ms	596480 KB	Output is correct
35	Correct	2678 ms	649644 KB	Output is correct
36	Correct	1822 ms	629500 KB	Output is correct
37	Correct	1530 ms	564188 KB	Output is correct
38	Correct	1205 ms	562352 KB	Output is correct
39	Correct	765 ms	557764 KB	Output is correct
40	Correct	750 ms	558216 KB	Output is correct
41	Correct	1183 ms	558948 KB	Output is correct
42	Correct	1242 ms	559360 KB	Output is correct
43	Correct	151 ms	556176 KB	Output is correct
44	Correct	1121 ms	559536 KB	Output is correct
45	Correct	978 ms	559184 KB	Output is correct
46	Correct	791 ms	559044 KB	Output is correct
47	Correct	578 ms	556992 KB	Output is correct
48	Correct	549 ms	557364 KB	Output is correct
49	Correct	699 ms	557260 KB	Output is correct
50	Correct	957 ms	558344 KB	Output is correct
51	Correct	654 ms	557284 KB	Output is correct

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4152 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

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

Subtask #5

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	548176 KB	Output is correct
2	Correct	108 ms	548204 KB	Output is correct
3	Correct	109 ms	548380 KB	Output is correct
4	Correct	109 ms	548428 KB	Output is correct
5	Correct	110 ms	548288 KB	Output is correct
6	Correct	114 ms	548748 KB	Output is correct
7	Correct	111 ms	548688 KB	Output is correct
8	Correct	116 ms	549204 KB	Output is correct
9	Correct	112 ms	549020 KB	Output is correct
10	Correct	114 ms	549152 KB	Output is correct
11	Correct	113 ms	548756 KB	Output is correct
12	Correct	114 ms	548688 KB	Output is correct
13	Correct	111 ms	548432 KB	Output is correct
14	Correct	110 ms	548444 KB	Output is correct
15	Correct	115 ms	548916 KB	Output is correct
16	Correct	113 ms	548832 KB	Output is correct
17	Correct	118 ms	548424 KB	Output is correct
18	Correct	113 ms	548612 KB	Output is correct
19	Correct	117 ms	548972 KB	Output is correct
20	Correct	113 ms	548508 KB	Output is correct
21	Correct	110 ms	548432 KB	Output is correct
22	Correct	114 ms	549132 KB	Output is correct
23	Correct	117 ms	549056 KB	Output is correct
24	Correct	114 ms	549000 KB	Output is correct
25	Correct	115 ms	548436 KB	Output is correct
26	Correct	114 ms	548288 KB	Output is correct
27	Correct	115 ms	548688 KB	Output is correct
28	Correct	119 ms	548436 KB	Output is correct
29	Correct	113 ms	548436 KB	Output is correct
30	Correct	112 ms	548432 KB	Output is correct
31	Correct	3249 ms	658752 KB	Output is correct
32	Correct	154 ms	554700 KB	Output is correct
33	Correct	1902 ms	586364 KB	Output is correct
34	Correct	3164 ms	596480 KB	Output is correct
35	Correct	2678 ms	649644 KB	Output is correct
36	Correct	1822 ms	629500 KB	Output is correct
37	Correct	1530 ms	564188 KB	Output is correct
38	Correct	1205 ms	562352 KB	Output is correct
39	Correct	765 ms	557764 KB	Output is correct
40	Correct	750 ms	558216 KB	Output is correct
41	Correct	1183 ms	558948 KB	Output is correct
42	Correct	1242 ms	559360 KB	Output is correct
43	Correct	151 ms	556176 KB	Output is correct
44	Correct	1121 ms	559536 KB	Output is correct
45	Correct	978 ms	559184 KB	Output is correct
46	Correct	791 ms	559044 KB	Output is correct
47	Correct	578 ms	556992 KB	Output is correct
48	Correct	549 ms	557364 KB	Output is correct
49	Correct	699 ms	557260 KB	Output is correct
50	Correct	957 ms	558344 KB	Output is correct
51	Correct	654 ms	557284 KB	Output is correct
52	Correct	1212 ms	673212 KB	Output is correct
53	Correct	1189 ms	603584 KB	Output is correct
54	Correct	2807 ms	681036 KB	Output is correct
55	Correct	1317 ms	598008 KB	Output is correct
56	Correct	1260 ms	617664 KB	Output is correct
57	Correct	1354 ms	570628 KB	Output is correct
58	Correct	1535 ms	598116 KB	Output is correct
59	Correct	1468 ms	618308 KB	Output is correct
60	Correct	1548 ms	570824 KB	Output is correct
61	Correct	208 ms	566464 KB	Output is correct
62	Correct	1216 ms	674304 KB	Output is correct
63	Correct	2193 ms	658588 KB	Output is correct
64	Correct	2770 ms	639200 KB	Output is correct
65	Correct	2997 ms	585228 KB	Output is correct
66	Correct	1452 ms	560712 KB	Output is correct
67	Correct	348 ms	556476 KB	Output is correct

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	548176 KB	Output is correct
2	Correct	108 ms	548204 KB	Output is correct
3	Correct	109 ms	548380 KB	Output is correct
4	Correct	109 ms	548428 KB	Output is correct
5	Correct	110 ms	548288 KB	Output is correct
6	Correct	114 ms	548748 KB	Output is correct
7	Correct	111 ms	548688 KB	Output is correct
8	Correct	116 ms	549204 KB	Output is correct
9	Correct	112 ms	549020 KB	Output is correct
10	Correct	114 ms	549152 KB	Output is correct
11	Correct	113 ms	548756 KB	Output is correct
12	Correct	114 ms	548688 KB	Output is correct
13	Correct	111 ms	548432 KB	Output is correct
14	Correct	110 ms	548444 KB	Output is correct
15	Correct	115 ms	548916 KB	Output is correct
16	Correct	113 ms	548832 KB	Output is correct
17	Correct	118 ms	548424 KB	Output is correct
18	Correct	113 ms	548612 KB	Output is correct
19	Correct	117 ms	548972 KB	Output is correct
20	Correct	113 ms	548508 KB	Output is correct
21	Correct	110 ms	548432 KB	Output is correct
22	Correct	114 ms	549132 KB	Output is correct
23	Correct	117 ms	549056 KB	Output is correct
24	Correct	114 ms	549000 KB	Output is correct
25	Correct	115 ms	548436 KB	Output is correct
26	Correct	114 ms	548288 KB	Output is correct
27	Correct	115 ms	548688 KB	Output is correct
28	Correct	119 ms	548436 KB	Output is correct
29	Correct	113 ms	548436 KB	Output is correct
30	Correct	112 ms	548432 KB	Output is correct
31	Correct	3249 ms	658752 KB	Output is correct
32	Correct	154 ms	554700 KB	Output is correct
33	Correct	1902 ms	586364 KB	Output is correct
34	Correct	3164 ms	596480 KB	Output is correct
35	Correct	2678 ms	649644 KB	Output is correct
36	Correct	1822 ms	629500 KB	Output is correct
37	Correct	1530 ms	564188 KB	Output is correct
38	Correct	1205 ms	562352 KB	Output is correct
39	Correct	765 ms	557764 KB	Output is correct
40	Correct	750 ms	558216 KB	Output is correct
41	Correct	1183 ms	558948 KB	Output is correct
42	Correct	1242 ms	559360 KB	Output is correct
43	Correct	151 ms	556176 KB	Output is correct
44	Correct	1121 ms	559536 KB	Output is correct
45	Correct	978 ms	559184 KB	Output is correct
46	Correct	791 ms	559044 KB	Output is correct
47	Correct	578 ms	556992 KB	Output is correct
48	Correct	549 ms	557364 KB	Output is correct
49	Correct	699 ms	557260 KB	Output is correct
50	Correct	957 ms	558344 KB	Output is correct
51	Correct	654 ms	557284 KB	Output is correct
52	Runtime error	4152 ms	1048576 KB	Execution killed with signal 9
53	Halted	0 ms	0 KB	-