oj.uz

답안 #979390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979390 2024-05-10T18:51:04 Z Jarif_Rahman 새 집 (APIO18_new_home) C++17
5 / 100
 1144 ms 1048576 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{
    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 = new Node();
    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 = new Node();
        if(!nd->r) nd->r = new Node();
        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;
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 767572 KB Output is correct
2 Correct 155 ms 767592 KB Output is correct
3 Correct 155 ms 767564 KB Output is correct
4 Correct 155 ms 767728 KB Output is correct
5 Correct 154 ms 767568 KB Output is correct
6 Correct 165 ms 772668 KB Output is correct
7 Correct 159 ms 769332 KB Output is correct
8 Correct 160 ms 771408 KB Output is correct
9 Correct 156 ms 769868 KB Output is correct
10 Correct 162 ms 773072 KB Output is correct
11 Correct 159 ms 770384 KB Output is correct
12 Correct 162 ms 772248 KB Output is correct
13 Correct 156 ms 769616 KB Output is correct
14 Correct 159 ms 770384 KB Output is correct
15 Correct 158 ms 770772 KB Output is correct
16 Correct 160 ms 770660 KB Output is correct
17 Correct 159 ms 770900 KB Output is correct
18 Correct 163 ms 770880 KB Output is correct
19 Correct 174 ms 770680 KB Output is correct
20 Correct 162 ms 771016 KB Output is correct
21 Correct 154 ms 767664 KB Output is correct
22 Correct 169 ms 770068 KB Output is correct
23 Correct 161 ms 770640 KB Output is correct
24 Correct 160 ms 770972 KB Output is correct
25 Correct 163 ms 771220 KB Output is correct
26 Correct 160 ms 771172 KB Output is correct
27 Correct 159 ms 767620 KB Output is correct
28 Correct 158 ms 770644 KB Output is correct
29 Correct 157 ms 770400 KB Output is correct
30 Correct 168 ms 769616 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 767572 KB Output is correct
2 Correct 155 ms 767592 KB Output is correct
3 Correct 155 ms 767564 KB Output is correct
4 Correct 155 ms 767728 KB Output is correct
5 Correct 154 ms 767568 KB Output is correct
6 Correct 165 ms 772668 KB Output is correct
7 Correct 159 ms 769332 KB Output is correct
8 Correct 160 ms 771408 KB Output is correct
9 Correct 156 ms 769868 KB Output is correct
10 Correct 162 ms 773072 KB Output is correct
11 Correct 159 ms 770384 KB Output is correct
12 Correct 162 ms 772248 KB Output is correct
13 Correct 156 ms 769616 KB Output is correct
14 Correct 159 ms 770384 KB Output is correct
15 Correct 158 ms 770772 KB Output is correct
16 Correct 160 ms 770660 KB Output is correct
17 Correct 159 ms 770900 KB Output is correct
18 Correct 163 ms 770880 KB Output is correct
19 Correct 174 ms 770680 KB Output is correct
20 Correct 162 ms 771016 KB Output is correct
21 Correct 154 ms 767664 KB Output is correct
22 Correct 169 ms 770068 KB Output is correct
23 Correct 161 ms 770640 KB Output is correct
24 Correct 160 ms 770972 KB Output is correct
25 Correct 163 ms 771220 KB Output is correct
26 Correct 160 ms 771172 KB Output is correct
27 Correct 159 ms 767620 KB Output is correct
28 Correct 158 ms 770644 KB Output is correct
29 Correct 157 ms 770400 KB Output is correct
30 Correct 168 ms 769616 KB Output is correct
31 Runtime error 1032 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 933 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1144 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 767572 KB Output is correct
2 Correct 155 ms 767592 KB Output is correct
3 Correct 155 ms 767564 KB Output is correct
4 Correct 155 ms 767728 KB Output is correct
5 Correct 154 ms 767568 KB Output is correct
6 Correct 165 ms 772668 KB Output is correct
7 Correct 159 ms 769332 KB Output is correct
8 Correct 160 ms 771408 KB Output is correct
9 Correct 156 ms 769868 KB Output is correct
10 Correct 162 ms 773072 KB Output is correct
11 Correct 159 ms 770384 KB Output is correct
12 Correct 162 ms 772248 KB Output is correct
13 Correct 156 ms 769616 KB Output is correct
14 Correct 159 ms 770384 KB Output is correct
15 Correct 158 ms 770772 KB Output is correct
16 Correct 160 ms 770660 KB Output is correct
17 Correct 159 ms 770900 KB Output is correct
18 Correct 163 ms 770880 KB Output is correct
19 Correct 174 ms 770680 KB Output is correct
20 Correct 162 ms 771016 KB Output is correct
21 Correct 154 ms 767664 KB Output is correct
22 Correct 169 ms 770068 KB Output is correct
23 Correct 161 ms 770640 KB Output is correct
24 Correct 160 ms 770972 KB Output is correct
25 Correct 163 ms 771220 KB Output is correct
26 Correct 160 ms 771172 KB Output is correct
27 Correct 159 ms 767620 KB Output is correct
28 Correct 158 ms 770644 KB Output is correct
29 Correct 157 ms 770400 KB Output is correct
30 Correct 168 ms 769616 KB Output is correct
31 Runtime error 1032 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 767572 KB Output is correct
2 Correct 155 ms 767592 KB Output is correct
3 Correct 155 ms 767564 KB Output is correct
4 Correct 155 ms 767728 KB Output is correct
5 Correct 154 ms 767568 KB Output is correct
6 Correct 165 ms 772668 KB Output is correct
7 Correct 159 ms 769332 KB Output is correct
8 Correct 160 ms 771408 KB Output is correct
9 Correct 156 ms 769868 KB Output is correct
10 Correct 162 ms 773072 KB Output is correct
11 Correct 159 ms 770384 KB Output is correct
12 Correct 162 ms 772248 KB Output is correct
13 Correct 156 ms 769616 KB Output is correct
14 Correct 159 ms 770384 KB Output is correct
15 Correct 158 ms 770772 KB Output is correct
16 Correct 160 ms 770660 KB Output is correct
17 Correct 159 ms 770900 KB Output is correct
18 Correct 163 ms 770880 KB Output is correct
19 Correct 174 ms 770680 KB Output is correct
20 Correct 162 ms 771016 KB Output is correct
21 Correct 154 ms 767664 KB Output is correct
22 Correct 169 ms 770068 KB Output is correct
23 Correct 161 ms 770640 KB Output is correct
24 Correct 160 ms 770972 KB Output is correct
25 Correct 163 ms 771220 KB Output is correct
26 Correct 160 ms 771172 KB Output is correct
27 Correct 159 ms 767620 KB Output is correct
28 Correct 158 ms 770644 KB Output is correct
29 Correct 157 ms 770400 KB Output is correct
30 Correct 168 ms 769616 KB Output is correct
31 Runtime error 1032 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -