oj.uz

Submission #979393

# Submission time Handle Problem Language Result Execution time Memory
979393 2024-05-10T19:12:03 Z Jarif_Rahman New Home (APIO18_new_home) C++17
10 / 100
 2459 ms 886964 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 = 1e7;

struct Node{
    ll inc = 0, dec = 0;
    bool binc = 0, bdec = 0;
    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 = max(nd->inc, x+a-l), nd->binc = 1;
            else nd->dec = max(nd->dec, x-a+l), nd->bdec = 1;
            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, ll x, bool inc){
        add(l, r, root, 0, n-1, x, inc);
    }

    ll get(int i){
        Node* nd = root;
        int a = 0, b = n-1;
        ll mx = 0;
        while(nd){
            if(nd->binc) mx = max(mx, nd->inc+i-a);
            if(nd->bdec) mx = max(mx, nd->dec-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;
    vector<set<int>> stores(k);
    vector<map<int, int>> cnt(k);
    sparse_segtree S(L);
    vector<int> cnt_t(k, 0);
    int nonzero = 0;

    for(int i = 0; i < n; i++){
        int x, t, a, b; cin >> x >> t >> a >> b; t--;
        stores[t].insert(x);
        cnt[t][x]++;
        cnt_t[t]++;
        if(cnt_t[t] == 1) nonzero++;
        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());

    for(auto s: stores){
        if(s.empty()){
            while(q--) cout << "-1\n";
            exit(0);
        }
        auto it = s.begin();
        S.add(0, *it, *it, false);
        for(; next(it) != s.end(); it++){
            int md = (*it+*next(it))/2;
            if(md > *it) S.add(*it+1, md, 1, true);
            S.add(md+1, *next(it), *next(it)-md-1, false);
        }
        S.add(*s.rbegin()+1, L-1, 1, true);
    }


    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){
        }
        else if(it == stores[t].begin()){
            S.add(0, *next(it), *next(it), false);
        }
        else if(next(it) == stores[t].end()){
            S.add(*prev(it)+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);
        }
        stores[t].erase(it);
    };

    vector<int> ans(q);

    for(auto [_, type, x, i]: queries){
        if(type == 0){
            continue;
        }
        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 391708 KB Output is correct
2 Correct 59 ms 391732 KB Output is correct
3 Correct 59 ms 391764 KB Output is correct
4 Incorrect 60 ms 391672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 391708 KB Output is correct
2 Correct 59 ms 391732 KB Output is correct
3 Correct 59 ms 391764 KB Output is correct
4 Incorrect 60 ms 391672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1543 ms 444396 KB Output is correct
2 Correct 1244 ms 437700 KB Output is correct
3 Correct 998 ms 469112 KB Output is correct
4 Correct 1435 ms 448952 KB Output is correct
5 Correct 1118 ms 449600 KB Output is correct
6 Correct 1229 ms 440052 KB Output is correct
7 Correct 836 ms 468276 KB Output is correct
8 Correct 1225 ms 448188 KB Output is correct
9 Correct 1374 ms 441932 KB Output is correct
10 Correct 1334 ms 437928 KB Output is correct
11 Correct 992 ms 436724 KB Output is correct
12 Correct 1131 ms 438988 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 391708 KB Output is correct
2 Correct 59 ms 391732 KB Output is correct
3 Correct 59 ms 391764 KB Output is correct
4 Incorrect 60 ms 391672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 391708 KB Output is correct
2 Correct 59 ms 391732 KB Output is correct
3 Correct 59 ms 391764 KB Output is correct
4 Incorrect 60 ms 391672 KB Output isn't correct
5 Halted 0 ms 0 KB -