Submission #968547

#	Time	Username	Problem	Language	Result	Execution time	Memory
968547		socpite	New Home (APIO18_new_home)	C++14	47 / 100	5095 ms	328700 KiB

new_home

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5+5;
const int INF = 1e9+5;

vector<pair<int, pair<int, int>>> ev;
vector<int> cp;
int n, q, k;

int ans[maxn];
int p[maxn], ty[maxn];
int L[maxn], Y[maxn];

multiset<int> st[4*maxn], pos[maxn];

void add_st(int ql, int qr, int val, int l = 0, int r = cp.size()-1, int id = 1){
    if(ql > qr)return;
    if(cp[l] > qr || cp[r] < ql)return;
    if(ql <= cp[l] && cp[r] <= qr)st[id].insert(val);
    else {
        int mid = (l+r)>>1;
        add_st(ql, qr, val, l, mid, id<<1);
        add_st(ql, qr, val, mid+1, r, id<<1|1);
    }
}

void del_st(int ql, int qr, int val, int l = 0, int r = cp.size()-1, int id = 1){
    if(ql > qr)return;
    if(cp[l] > qr || cp[r] < ql)return;
    if(ql <= cp[l] && cp[r] <= qr)st[id].erase(st[id].find(val));
    else {
        int mid = (l+r)>>1;
        del_st(ql, qr, val, l, mid, id<<1);
        del_st(ql, qr, val, mid+1, r, id<<1|1);
    }
}

pair<int, int> get(int pos, int l = 0, int r = cp.size()-1, int id = 1){
    pair<int, int> re = make_pair(st[id].empty() ? -INF : max(*st[id].rbegin() - pos, pos - *st[id].begin()), st[id].size());
    if(l < r){
        int mid = (l+r)>>1;
        pair<int, int> tmp = pos <= cp[mid] ? get(pos, l, mid, id<<1) : get(pos, mid+1, r, id<<1|1);
        re.first = max(re.first, tmp.first);
        re.second += tmp.second;
    }
    return re;
}

void add_range(int l, int r){
    if(l == -INF)add_st(-INF, r, r);
    else if(r == INF)add_st(l+1, INF, l);
    else {
        int mid = (l+r)/2;
        add_st(l+1, mid, l);
        add_st(mid+1, r, r);
    }
}

void del_range(int l, int r){
    if(l == -INF)del_st(-INF, r, r);
    else if(r == INF)del_st(l+1, INF, l);
    else {
        int mid = (l+r)/2;
        del_st(l+1, mid, l);
        del_st(mid+1, r, r);
    }
}

void add(int x, int col){
    auto it = pos[col].insert(x);
    if(pos[col].size() == 1){
        add_range(-INF, x);
        add_range(x, INF);
    }
    else {
        if(next(it) == pos[col].end()){
            del_range(*prev(it), INF);
            add_range(*prev(it), x);
            add_range(x, INF);
        }
        else if(it == pos[col].begin()){
            del_range(-INF, *next(it));
            add_range(-INF, x);
            add_range(x, *next(it));
        }
        else {
            del_range(*prev(it), *next(it));
            add_range(*prev(it), *it);
            add_range(*it, *next(it));
        }
    }
}

void del(int x, int col){
    auto it = pos[col].erase(pos[col].find(x));
    if(pos[col].size() == 0){
        del_range(-INF, x);
        del_range(x, INF);
    }
    else {
        if(it == pos[col].end()){
            del_range(x, INF);
            del_range(*prev(it), x);
            add_range(*prev(it), INF);
        }
        else if(it == pos[col].begin()){
            del_range(-INF, x);
            del_range(x, *it);
            add_range(-INF, *it);
        }
        else {
            del_range(x, *it);
            del_range(*prev(it), x);
            add_range(*prev(it), *it);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >> p[i] >> ty[i] >> a >> b;
        ev.push_back({a, {0, i}});
        ev.push_back({b+1, {1, i}});
    }
    for(int i = 1; i <= q; i++){
        cin >> L[i] >> Y[i];
        ev.push_back({Y[i], {2, i}});
        cp.push_back(L[i]);
    }
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    sort(ev.begin(), ev.end());
    for(auto ele: ev){
        pair<int, int> event = ele.second;
        if(event.first == 0)add(p[event.second], ty[event.second]);
        else if(event.first == 1)del(p[event.second], ty[event.second]);
        else {
            pair<int, int> tmp = get(L[event.second]);
            ans[event.second] = tmp.second == k ? tmp.first : -1;
        }
    }
    for(int i = 1; i <= q; i++)cout << ans[i] << "\n";
}

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