Submission #979348

#	Time	Username	Problem	Language	Result	Execution time	Memory
979348		Jarif_Rahman	New Home (APIO18_new_home)	C++17	0 / 100	457 ms	342236 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 = 1e6;

struct Node{
    multiset<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.insert(x+a-l);
            else nd->dec.insert(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.erase(nd->inc.find(x+a-l));
            else nd->dec.erase(nd->dec.find(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())+i-a);
            if(!nd->dec.empty()) mx = max(mx, *(nd->dec.rbegin())-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<vector<int>> stores(k);
    for(int i = 0; i < n; i++){
        int x, t, a, b; cin >> x >> t >> a >> b; t--;
        stores[t].push_back(x);
    }
    for(auto &s: stores) sort(s.begin(), s.end());

    sparse_segtree S(L);
    for(auto s: stores){
        if(s.empty()){
            while(q--) cout << "-1\n";
            exit(0);
        }
        int m = s.size();
        S.add(0, s[0], s[0], false); //abs(0-s[0])
        for(int i = 0; i+1 < m; i++){
            int md = (s[i]+s[i+1])/2;
            if(md > s[i]) S.add(s[i]+1, md, 1, true);
            S.add(md+1, s[i+1], s[i+1]-md-1, false);
        }
        S.add(s[m-1]+1, L-1, 1, true);
    }

    while(q--){
        int l, y; cin >> l >> y;
        cout << S.get(l) << "\n";
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20