oj.uz

Submission #1107868

# Submission time Handle Problem Language Result Execution time Memory
1107868 2024-11-02T08:47:22 Z mispertion New Home (APIO18_new_home) C++17
57 / 100
 4885 ms 833808 KB 
#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 = 5e6 + 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{
    int t[M], l[M], r[M];
    int cur = 0;

    segtree(){
        t[0] = -infi;
        l[0] = -1;
        r[0] = -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] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            zer(l[v], tl, tm, i);
        }else{
            if(r[v] == -1){
                r[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -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] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            add(l[v], tl, tm, i, x);
        }else{
            if(r[v] == -1){
                r[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -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';
    }

    void sett(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] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            sett(l[v], tl, tm, i, x);
        }else{
            if(r[v] == -1){
                r[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            sett(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){
    auto da = spl.find(i);
    auto ha = spr.find(i);
    auto ed = (--da->S.end());
    auto hd = (--ha->S.end());
    if(*ed == x1){
        da->S.erase(ed);
        if(da->S.size() > 0){
            lt.sett(0, L, R, i, *(--da->S.end()));
        }else{
            lt.zer(0, L, R, i);
        }
    }else{
        da->S.erase(da->S.find(x1));
    }
    if(*hd == x2){
        ha->S.erase(hd);
        if(ha->S.size() > 0)
            rt.sett(0, L, R, i, *(--ha->S.end()));
        else
            rt.zer(0, L, R, i);
    }else{
        ha->S.erase(ha->S.find(x2));
    }
}

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;
                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++;
            }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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37200 KB Output is correct
2 Correct 6 ms 37368 KB Output is correct
3 Correct 6 ms 37200 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 7 ms 37360 KB Output is correct
6 Correct 8 ms 37712 KB Output is correct
7 Correct 6 ms 37456 KB Output is correct
8 Correct 8 ms 37588 KB Output is correct
9 Correct 6 ms 37508 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37604 KB Output is correct
13 Correct 6 ms 37332 KB Output is correct
14 Correct 7 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 7 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 6 ms 37456 KB Output is correct
19 Correct 6 ms 37456 KB Output is correct
20 Correct 8 ms 37416 KB Output is correct
21 Correct 6 ms 37516 KB Output is correct
22 Correct 6 ms 37456 KB Output is correct
23 Correct 6 ms 37456 KB Output is correct
24 Correct 6 ms 37620 KB Output is correct
25 Correct 7 ms 37456 KB Output is correct
26 Correct 7 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 6 ms 37456 KB Output is correct
29 Correct 6 ms 37456 KB Output is correct
30 Correct 6 ms 37468 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37200 KB Output is correct
2 Correct 6 ms 37368 KB Output is correct
3 Correct 6 ms 37200 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 7 ms 37360 KB Output is correct
6 Correct 8 ms 37712 KB Output is correct
7 Correct 6 ms 37456 KB Output is correct
8 Correct 8 ms 37588 KB Output is correct
9 Correct 6 ms 37508 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37604 KB Output is correct
13 Correct 6 ms 37332 KB Output is correct
14 Correct 7 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 7 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 6 ms 37456 KB Output is correct
19 Correct 6 ms 37456 KB Output is correct
20 Correct 8 ms 37416 KB Output is correct
21 Correct 6 ms 37516 KB Output is correct
22 Correct 6 ms 37456 KB Output is correct
23 Correct 6 ms 37456 KB Output is correct
24 Correct 6 ms 37620 KB Output is correct
25 Correct 7 ms 37456 KB Output is correct
26 Correct 7 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 6 ms 37456 KB Output is correct
29 Correct 6 ms 37456 KB Output is correct
30 Correct 6 ms 37468 KB Output is correct
31 Correct 946 ms 172976 KB Output is correct
32 Correct 104 ms 46776 KB Output is correct
33 Correct 893 ms 168748 KB Output is correct
34 Correct 955 ms 158384 KB Output is correct
35 Correct 1075 ms 175516 KB Output is correct
36 Correct 1072 ms 174644 KB Output is correct
37 Correct 582 ms 165740 KB Output is correct
38 Correct 625 ms 166200 KB Output is correct
39 Correct 448 ms 160432 KB Output is correct
40 Correct 513 ms 165040 KB Output is correct
41 Correct 433 ms 100272 KB Output is correct
42 Correct 466 ms 102300 KB Output is correct
43 Correct 74 ms 48816 KB Output is correct
44 Correct 451 ms 102300 KB Output is correct
45 Correct 417 ms 102320 KB Output is correct
46 Correct 377 ms 102320 KB Output is correct
47 Correct 213 ms 90032 KB Output is correct
48 Correct 222 ms 97456 KB Output is correct
49 Correct 254 ms 99308 KB Output is correct
50 Correct 284 ms 98852 KB Output is correct
51 Correct 262 ms 99508 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2745 ms 278460 KB Output is correct
2 Correct 1764 ms 309296 KB Output is correct
3 Correct 759 ms 141764 KB Output is correct
4 Correct 2496 ms 257996 KB Output is correct
5 Correct 1699 ms 313792 KB Output is correct
6 Correct 1546 ms 310012 KB Output is correct
7 Correct 726 ms 141320 KB Output is correct
8 Correct 2643 ms 259232 KB Output is correct
9 Correct 2888 ms 301440 KB Output is correct
10 Correct 1989 ms 312988 KB Output is correct
11 Correct 1416 ms 304216 KB Output is correct
12 Correct 1618 ms 312092 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 4885 ms 833808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37200 KB Output is correct
2 Correct 6 ms 37368 KB Output is correct
3 Correct 6 ms 37200 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 7 ms 37360 KB Output is correct
6 Correct 8 ms 37712 KB Output is correct
7 Correct 6 ms 37456 KB Output is correct
8 Correct 8 ms 37588 KB Output is correct
9 Correct 6 ms 37508 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37604 KB Output is correct
13 Correct 6 ms 37332 KB Output is correct
14 Correct 7 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 7 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 6 ms 37456 KB Output is correct
19 Correct 6 ms 37456 KB Output is correct
20 Correct 8 ms 37416 KB Output is correct
21 Correct 6 ms 37516 KB Output is correct
22 Correct 6 ms 37456 KB Output is correct
23 Correct 6 ms 37456 KB Output is correct
24 Correct 6 ms 37620 KB Output is correct
25 Correct 7 ms 37456 KB Output is correct
26 Correct 7 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 6 ms 37456 KB Output is correct
29 Correct 6 ms 37456 KB Output is correct
30 Correct 6 ms 37468 KB Output is correct
31 Correct 946 ms 172976 KB Output is correct
32 Correct 104 ms 46776 KB Output is correct
33 Correct 893 ms 168748 KB Output is correct
34 Correct 955 ms 158384 KB Output is correct
35 Correct 1075 ms 175516 KB Output is correct
36 Correct 1072 ms 174644 KB Output is correct
37 Correct 582 ms 165740 KB Output is correct
38 Correct 625 ms 166200 KB Output is correct
39 Correct 448 ms 160432 KB Output is correct
40 Correct 513 ms 165040 KB Output is correct
41 Correct 433 ms 100272 KB Output is correct
42 Correct 466 ms 102300 KB Output is correct
43 Correct 74 ms 48816 KB Output is correct
44 Correct 451 ms 102300 KB Output is correct
45 Correct 417 ms 102320 KB Output is correct
46 Correct 377 ms 102320 KB Output is correct
47 Correct 213 ms 90032 KB Output is correct
48 Correct 222 ms 97456 KB Output is correct
49 Correct 254 ms 99308 KB Output is correct
50 Correct 284 ms 98852 KB Output is correct
51 Correct 262 ms 99508 KB Output is correct
52 Correct 204 ms 59868 KB Output is correct
53 Correct 174 ms 50864 KB Output is correct
54 Correct 553 ms 98736 KB Output is correct
55 Correct 368 ms 89264 KB Output is correct
56 Correct 315 ms 86452 KB Output is correct
57 Correct 452 ms 100144 KB Output is correct
58 Correct 381 ms 85680 KB Output is correct
59 Correct 335 ms 84192 KB Output is correct
60 Correct 437 ms 101808 KB Output is correct
61 Correct 148 ms 60064 KB Output is correct
62 Correct 188 ms 59832 KB Output is correct
63 Correct 402 ms 78352 KB Output is correct
64 Correct 491 ms 88752 KB Output is correct
65 Correct 500 ms 100496 KB Output is correct
66 Correct 428 ms 100248 KB Output is correct
67 Correct 206 ms 49328 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37200 KB Output is correct
2 Correct 6 ms 37368 KB Output is correct
3 Correct 6 ms 37200 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 7 ms 37360 KB Output is correct
6 Correct 8 ms 37712 KB Output is correct
7 Correct 6 ms 37456 KB Output is correct
8 Correct 8 ms 37588 KB Output is correct
9 Correct 6 ms 37508 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37604 KB Output is correct
13 Correct 6 ms 37332 KB Output is correct
14 Correct 7 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 7 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 6 ms 37456 KB Output is correct
19 Correct 6 ms 37456 KB Output is correct
20 Correct 8 ms 37416 KB Output is correct
21 Correct 6 ms 37516 KB Output is correct
22 Correct 6 ms 37456 KB Output is correct
23 Correct 6 ms 37456 KB Output is correct
24 Correct 6 ms 37620 KB Output is correct
25 Correct 7 ms 37456 KB Output is correct
26 Correct 7 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 6 ms 37456 KB Output is correct
29 Correct 6 ms 37456 KB Output is correct
30 Correct 6 ms 37468 KB Output is correct
31 Correct 946 ms 172976 KB Output is correct
32 Correct 104 ms 46776 KB Output is correct
33 Correct 893 ms 168748 KB Output is correct
34 Correct 955 ms 158384 KB Output is correct
35 Correct 1075 ms 175516 KB Output is correct
36 Correct 1072 ms 174644 KB Output is correct
37 Correct 582 ms 165740 KB Output is correct
38 Correct 625 ms 166200 KB Output is correct
39 Correct 448 ms 160432 KB Output is correct
40 Correct 513 ms 165040 KB Output is correct
41 Correct 433 ms 100272 KB Output is correct
42 Correct 466 ms 102300 KB Output is correct
43 Correct 74 ms 48816 KB Output is correct
44 Correct 451 ms 102300 KB Output is correct
45 Correct 417 ms 102320 KB Output is correct
46 Correct 377 ms 102320 KB Output is correct
47 Correct 213 ms 90032 KB Output is correct
48 Correct 222 ms 97456 KB Output is correct
49 Correct 254 ms 99308 KB Output is correct
50 Correct 284 ms 98852 KB Output is correct
51 Correct 262 ms 99508 KB Output is correct
52 Correct 2745 ms 278460 KB Output is correct
53 Correct 1764 ms 309296 KB Output is correct
54 Correct 759 ms 141764 KB Output is correct
55 Correct 2496 ms 257996 KB Output is correct
56 Correct 1699 ms 313792 KB Output is correct
57 Correct 1546 ms 310012 KB Output is correct
58 Correct 726 ms 141320 KB Output is correct
59 Correct 2643 ms 259232 KB Output is correct
60 Correct 2888 ms 301440 KB Output is correct
61 Correct 1989 ms 312988 KB Output is correct
62 Correct 1416 ms 304216 KB Output is correct
63 Correct 1618 ms 312092 KB Output is correct
64 Runtime error 4885 ms 833808 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -