Submission #979394

#	Time	Username	Problem	Language	Result	Execution time	Memory
979394		Jarif_Rahman	New Home (APIO18_new_home)	C++17	33 / 100	2527 ms	871508 KiB

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 = 2e7;

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
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20