Submission #1107755

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1107755	2024-11-02T04:51:34 Z	mispertion	New Home (APIO18_new_home)	C++17	10 / 100	4073 ms	643492 KB

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 zer(int v, int tl, int tr, int i){
        if(tl == tr){
            t[v] = -infi;
            //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);
            }
            zer(l[v], tl, tm, i);
        }else{
            if(r[v] == -1){
                r[v] = t.size();
                t.push_back(-infi);
                l.push_back(-1);
                r.push_back(-1);
            }
            zer(r[v], tm + 1, tr, i);
        }
        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]]);
    }

    void add(int v, int tl, int tr, int i, int x){
        if(tl == tr){
            t[v] = max(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];
map<int, multiset<int>> spl, spr;
segtree lt = segtree(), rt = segtree();

void add(int i, int x1, int x2){
    lt.add(0, L, R, i, x1);
    rt.add(0, L, R, i, x2);
    spl[i].insert(x1);
    spr[i].insert(x2);
}

void rem(int i, int x1, int x2){
    lt.zer(0, L, R, i);
    rt.zer(0, L, R, i);
    spl[i].erase(spl[i].find(x1));
    spr[i].erase(spr[i].find(x2));
    if(spl[i].size() > 0)
        lt.add(0, L, R, i, *(--spl[i].end()));
    if(spr[i].size() > 0)
        rt.add(0, L, R, i, *(--spr[i].end()));
}

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());
    int cnt = k;
    for(auto ev : evs){
        //cout << ev.F.F << ' ' << ev.F.S << ' ' << ev.S.F << ' ' << ev.S.S << '\n';
        if(ev.F.S == 1){
            int x = ev.S.F, tp = ev.S.S;
            if(cr[tp].find(x) != cr[tp].end()){
                cr[tp].insert(x);
                continue;
            }
            if(cr[tp].size() == 0){
                cr[tp].insert(x);
                add(L, x, x - 2 * L);
                add(R, 2 * R - x, -x);
                cnt--;
                continue;
            }
            int l = -1, r = -1;
            auto it = cr[tp].upper_bound(x);
            if(it != cr[tp].end()){
                add(((*it) + x) / 2, *it, -x);
                r = *it;
            }else{
                add(R, 2 * R - x, -x);
            }
            it = cr[tp].lower_bound(x);
            if(it != cr[tp].begin()){
                it--;
                add((x + (*it)) / 2, x, -(*it));
                l = *it;
            }else{
                add(L, x, x - 2 * L);
            }
            if(l != -1 && r != -1){
                rem((r + l) / 2, r, -l);
            }
            if(r == -1 && l != -1){
                rem(R, 2 * R - l, -l);
            }
            if(r != -1 && l == -1){
                rem(L, r, r - 2 * L);
            }
            cr[tp].insert(x);
        }else if(ev.F.S == -1){
            int x = ev.S.F, tp = ev.S.S;
            int l = -1, r = -1;
            if(cr[tp].count(x) > 1){
                cr[tp].erase(cr[tp].find(x));
                continue;
            }
            auto it = cr[tp].upper_bound(x);
            if(it != cr[tp].end()){
                r = *it;
                if(spl[(r + x) / 2].find(r) == spl[(r + x) / 2].end()){
                    cout << "AWODIJAOIWJD\n";
                    exit(0);
                }
                rem((r + x) / 2, r, -x);
            }else{
                rem(R, 2 * R - x, -x);
            }
            it = cr[tp].lower_bound(x);
            if(it != cr[tp].begin()){
                it--;
                l = (*it);
                rem((x + l) / 2, x, -l);
            }else{
                rem(L, x, x - 2 * L);
            }
            cr[tp].erase(cr[tp].find(x));
            if(l == -1 && r == -1){
                cnt++;
                assert(cr[tp].size() == 0);
            }else if(l == -1){
                add(L, r, r - 2 * L);
            }else if(r == -1){
                add(R, 2 * r - l, -l);
            }else{
                add((r + l) / 2, r, -l);
            }
        }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);
        }    
        //cout << cnt << '\n';   
    }
    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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	25168 KB	Output is correct
2	Runtime error	43 ms	50772 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	25168 KB	Output is correct
2	Runtime error	43 ms	50772 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3861 ms	315396 KB	Output is correct
2	Correct	2386 ms	320644 KB	Output is correct
3	Correct	1136 ms	129184 KB	Output is correct
4	Correct	3727 ms	312052 KB	Output is correct
5	Correct	2232 ms	323588 KB	Output is correct
6	Correct	2287 ms	321188 KB	Output is correct
7	Correct	1120 ms	129112 KB	Output is correct
8	Correct	3795 ms	310972 KB	Output is correct
9	Correct	4073 ms	317600 KB	Output is correct
10	Correct	2695 ms	322440 KB	Output is correct
11	Correct	2364 ms	317716 KB	Output is correct
12	Correct	2664 ms	319228 KB	Output is correct