Submission #1107631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107631		mispertion	New Home (APIO18_new_home)	C++17	0 / 100	4316 ms	385572 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
using ld = long double;
using pii = pair<int, int>;
#define F first
#define S second

const ld PI = 3.1415926535;
const int N = 5e5 + 2;
const int M = 2e6 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) {
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}


ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

struct segtree{
    vector<int> t, l, r;

    segtree(){
        t.assign(1, -infi);
        l.assign(1, -1);
        r.assign(1, -1);
    }

    void add(int v, int tl, int tr, int i, int x){
        if(tl == tr){
            t[v] = x;
            //cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
            return;
        }
        int tm = (tl + tr) / 2;
        if(i <= tm){
            if(l[v] == -1){
                l[v] = t.size();
                t.push_back(-infi);
                l.push_back(-1);
                r.push_back(-1);
            }
            add(l[v], tl, tm, i, x);
        }else{
            if(r[v] == -1){
                r[v] = t.size();
                t.push_back(-infi);
                l.push_back(-1);
                r.push_back(-1);
            }
            add(r[v], tm + 1, tr, i, x);
        }
        t[v] = -infi;
        if(l[v] != -1)
            t[v] = max(t[v], t[l[v]]);
        if(r[v] != -1)
            t[v] = max(t[v], t[r[v]]);
        //cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
    }

    int get(int v, int tl, int tr, int lu, int ru){
        if(v == -1)
            return -infi;
        if(tl > ru || lu > tr)
            return -infi;
        if(lu <= tl && tr <= ru)
            return t[v];
        int tm = (tl + tr) / 2;
        return max(get(l[v], tl, tm, lu, ru), get(r[v], tm + 1, tr, lu, ru));
    }
};

int n, q, k, ans[N], L = 0, R = 2e8;
vector<pair<pii, pii>> evs;
multiset<int> cr[N];

void solve() {
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        int x, tp, a, b;
        cin >> x >> tp >> a >> b;
        x *= 2;
        evs.push_back({{a, 1}, {x, tp}});
        evs.push_back({{b + 1, -1}, {x, tp}});
    }
    for(int i = 1; i <= q; i++){
        int l, y;
        cin >> l >> y;
        l *= 2;
        evs.push_back({{y, 2}, {l, i}});
    }
    sort(evs.begin(), evs.end());
    segtree lt = segtree(), rt = segtree();
    int cnt = k;
    for(auto ev : evs){
        if(ev.F.S == 1){
            int x = ev.S.F, tp = ev.S.S;
            if(cr[tp].size() == 0){
                cr[tp].insert(x);
                lt.add(0, L, R, L, x);
                lt.add(0, L, R, R, 2 * R - x);
                rt.add(0, L, R, R, -x);
                rt.add(0, L, R, L, x - 2 * L);
                cnt--;
                continue;
            }
            int l = -1, r = -1;
            auto it = cr[tp].upper_bound(x);
            if(it != cr[tp].end()){
                lt.add(0, L, R, ((*it) + x) / 2, *it);
                rt.add(0, L, R, ((*it) + x) / 2, -x);
                r = *it;
            }else{
                lt.add(0, L, R, R, 2 * R - x);
                rt.add(0, L, R, R, -x);
            }
            it = cr[tp].lower_bound(x);
            if(it != cr[tp].begin()){
                it--;
                lt.add(0, L, R, (x + (*it)) / 2, x);
                rt.add(0, L, R, (x + (*it)) / 2, -(*it));
                l = *it;
            }else{
                lt.add(0, L, R, L, x);
                rt.add(0, L, R, L, x - 2 * L);
            }
            if(l != -1 && r != -1){
                lt.add(0, L, R, (r + l) / 2, -infi);
                rt.add(0, L, R, (r + l) / 2, -infi);
            }
            cr[tp].insert(x);
        }else if(ev.F.S == -1){
            int x = ev.S.F, tp = ev.S.S;
            int l = -1, r = -1;
            auto it = cr[tp].upper_bound(x);
            if(it != cr[tp].end()){
                r = *it;
                lt.add(0, L, R, (r + x) / 2, -infi);
                rt.add(0, L, R, (r + x) / 2, -infi);
            }else{
                lt.add(0, L, R, R, -infi);
                rt.add(0, L, R, R, -infi);
            }
            it = cr[tp].lower_bound(x);
            if(it != cr[tp].begin()){
                it--;
                l = (*it);
                lt.add(0, L, R, (x + l) / 2, -infi);
                rt.add(0, L, R, (x + l) / 2, -infi);
            }else{
                lt.add(0, L, R, L, -infi);
                rt.add(0, L, R, L, -infi);
            }
            if(l == -1 && r == -1){
                if(cr[tp].size() == 1){
                    cnt++;
                    lt.add(0, L, R, L, -infi);
                    lt.add(0, L, R, R, -infi);
                    rt.add(0, L, R, L, -infi);
                    rt.add(0, L, R, R, -infi);
                }else{
                    lt.add(0, L, R, L, x);
                    lt.add(0, L, R, R, 2 * R - x);
                    rt.add(0, L, R, R, -x);
                    rt.add(0, L, R, L, x - 2 * L);
                }
            }else if(l == -1){
                lt.add(0, L, R, L, r);
                rt.add(0, L, R, L, r - 2 * L);
            }else if(r == -1){
                lt.add(0, L, R, R, 2 * R - l);
                rt.add(0, L, R, R, -l);
            }else{
                lt.add(0, L, R, (r + l) / 2, r);
                rt.add(0, L, R, (r + l) / 2, -l);
            }
            cr[tp].erase(cr[tp].find(x));
        }else{
            int x = ev.S.F, i = ev.S.S;
            int ret = max(lt.get(0, L, R, L, x) - x, rt.get(0, L, R, x, R) + x);
            if(cnt != 0)
                ans[i] = -1;
            else
                ans[i] = (ret < 0 ? -1 : ret / 2);
        }       
    }
    for(int i = 1; i <=q; i++)
        cout << ans[i] << ' ';
    cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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