Submission #979785

#	Time	Username	Problem	Language	Result	Execution time	Memory
979785		Jarif_Rahman	New Home (APIO18_new_home)	C++17	Compilation error	0 ms	0 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 = 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];
multiset<int> mx[2][L];
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;

    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";
}

Compilation message (stderr)

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status