oj.uz

Submission #1107878

# Submission time Handle Problem Language Result Execution time Memory
1107878 2024-11-02T09:14:57 Z mispertion New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 326472 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
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 = 1e7 + 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 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.sett(0, L, R, i, -infi);
        }
    }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.sett(0, L, R, i, -infi);
    }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 5 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 6 ms 35152 KB Output is correct
4 Correct 5 ms 35152 KB Output is correct
5 Correct 6 ms 35416 KB Output is correct
6 Correct 9 ms 37456 KB Output is correct
7 Correct 6 ms 35408 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 8 ms 37456 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 6 ms 37456 KB Output is correct
16 Correct 8 ms 37328 KB Output is correct
17 Correct 8 ms 37468 KB Output is correct
18 Correct 8 ms 37468 KB Output is correct
19 Correct 8 ms 37456 KB Output is correct
20 Correct 7 ms 37560 KB Output is correct
21 Correct 6 ms 35264 KB Output is correct
22 Correct 6 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37340 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 35576 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 6 ms 37456 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 6 ms 35152 KB Output is correct
4 Correct 5 ms 35152 KB Output is correct
5 Correct 6 ms 35416 KB Output is correct
6 Correct 9 ms 37456 KB Output is correct
7 Correct 6 ms 35408 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 8 ms 37456 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 6 ms 37456 KB Output is correct
16 Correct 8 ms 37328 KB Output is correct
17 Correct 8 ms 37468 KB Output is correct
18 Correct 8 ms 37468 KB Output is correct
19 Correct 8 ms 37456 KB Output is correct
20 Correct 7 ms 37560 KB Output is correct
21 Correct 6 ms 35264 KB Output is correct
22 Correct 6 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37340 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 35576 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 6 ms 37456 KB Output is correct
31 Correct 902 ms 119460 KB Output is correct
32 Correct 97 ms 41416 KB Output is correct
33 Correct 800 ms 115368 KB Output is correct
34 Correct 1040 ms 113056 KB Output is correct
35 Correct 956 ms 120676 KB Output is correct
36 Correct 958 ms 121248 KB Output is correct
37 Correct 515 ms 112288 KB Output is correct
38 Correct 535 ms 112780 KB Output is correct
39 Correct 415 ms 110904 KB Output is correct
40 Correct 455 ms 111784 KB Output is correct
41 Correct 426 ms 73652 KB Output is correct
42 Correct 452 ms 69532 KB Output is correct
43 Correct 105 ms 31156 KB Output is correct
44 Correct 477 ms 74140 KB Output is correct
45 Correct 413 ms 77736 KB Output is correct
46 Correct 364 ms 77504 KB Output is correct
47 Correct 215 ms 67512 KB Output is correct
48 Correct 216 ms 68764 KB Output is correct
49 Correct 254 ms 72344 KB Output is correct
50 Correct 272 ms 69304 KB Output is correct
51 Correct 275 ms 74936 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2661 ms 207740 KB Output is correct
2 Correct 1588 ms 228588 KB Output is correct
3 Correct 795 ms 123560 KB Output is correct
4 Correct 2673 ms 195780 KB Output is correct
5 Correct 1595 ms 228008 KB Output is correct
6 Correct 1429 ms 228512 KB Output is correct
7 Correct 746 ms 123560 KB Output is correct
8 Correct 2622 ms 195868 KB Output is correct
9 Correct 2759 ms 214696 KB Output is correct
10 Correct 1965 ms 227184 KB Output is correct
11 Correct 1427 ms 222620 KB Output is correct
12 Correct 1668 ms 228464 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4854 ms 301920 KB Output is correct
2 Correct 2210 ms 69368 KB Output is correct
3 Correct 4463 ms 326472 KB Output is correct
4 Correct 1108 ms 135244 KB Output is correct
5 Correct 4120 ms 241988 KB Output is correct
6 Correct 3646 ms 220928 KB Output is correct
7 Correct 3641 ms 325664 KB Output is correct
8 Correct 4038 ms 326416 KB Output is correct
9 Correct 1147 ms 136624 KB Output is correct
10 Correct 3892 ms 234928 KB Output is correct
11 Correct 4410 ms 297800 KB Output is correct
12 Execution timed out 5024 ms 325028 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 6 ms 35152 KB Output is correct
4 Correct 5 ms 35152 KB Output is correct
5 Correct 6 ms 35416 KB Output is correct
6 Correct 9 ms 37456 KB Output is correct
7 Correct 6 ms 35408 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 8 ms 37456 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 6 ms 37456 KB Output is correct
16 Correct 8 ms 37328 KB Output is correct
17 Correct 8 ms 37468 KB Output is correct
18 Correct 8 ms 37468 KB Output is correct
19 Correct 8 ms 37456 KB Output is correct
20 Correct 7 ms 37560 KB Output is correct
21 Correct 6 ms 35264 KB Output is correct
22 Correct 6 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37340 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 35576 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 6 ms 37456 KB Output is correct
31 Correct 902 ms 119460 KB Output is correct
32 Correct 97 ms 41416 KB Output is correct
33 Correct 800 ms 115368 KB Output is correct
34 Correct 1040 ms 113056 KB Output is correct
35 Correct 956 ms 120676 KB Output is correct
36 Correct 958 ms 121248 KB Output is correct
37 Correct 515 ms 112288 KB Output is correct
38 Correct 535 ms 112780 KB Output is correct
39 Correct 415 ms 110904 KB Output is correct
40 Correct 455 ms 111784 KB Output is correct
41 Correct 426 ms 73652 KB Output is correct
42 Correct 452 ms 69532 KB Output is correct
43 Correct 105 ms 31156 KB Output is correct
44 Correct 477 ms 74140 KB Output is correct
45 Correct 413 ms 77736 KB Output is correct
46 Correct 364 ms 77504 KB Output is correct
47 Correct 215 ms 67512 KB Output is correct
48 Correct 216 ms 68764 KB Output is correct
49 Correct 254 ms 72344 KB Output is correct
50 Correct 272 ms 69304 KB Output is correct
51 Correct 275 ms 74936 KB Output is correct
52 Correct 172 ms 53688 KB Output is correct
53 Correct 154 ms 44688 KB Output is correct
54 Correct 482 ms 76216 KB Output is correct
55 Correct 325 ms 71084 KB Output is correct
56 Correct 302 ms 66984 KB Output is correct
57 Correct 407 ms 71356 KB Output is correct
58 Correct 431 ms 69304 KB Output is correct
59 Correct 361 ms 65460 KB Output is correct
60 Correct 459 ms 70644 KB Output is correct
61 Correct 158 ms 53944 KB Output is correct
62 Correct 171 ms 53660 KB Output is correct
63 Correct 415 ms 64024 KB Output is correct
64 Correct 463 ms 72288 KB Output is correct
65 Correct 566 ms 71612 KB Output is correct
66 Correct 401 ms 75624 KB Output is correct
67 Correct 208 ms 42168 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 6 ms 35152 KB Output is correct
4 Correct 5 ms 35152 KB Output is correct
5 Correct 6 ms 35416 KB Output is correct
6 Correct 9 ms 37456 KB Output is correct
7 Correct 6 ms 35408 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 37712 KB Output is correct
11 Correct 8 ms 37456 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 6 ms 37456 KB Output is correct
16 Correct 8 ms 37328 KB Output is correct
17 Correct 8 ms 37468 KB Output is correct
18 Correct 8 ms 37468 KB Output is correct
19 Correct 8 ms 37456 KB Output is correct
20 Correct 7 ms 37560 KB Output is correct
21 Correct 6 ms 35264 KB Output is correct
22 Correct 6 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37340 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 35576 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 6 ms 37456 KB Output is correct
31 Correct 902 ms 119460 KB Output is correct
32 Correct 97 ms 41416 KB Output is correct
33 Correct 800 ms 115368 KB Output is correct
34 Correct 1040 ms 113056 KB Output is correct
35 Correct 956 ms 120676 KB Output is correct
36 Correct 958 ms 121248 KB Output is correct
37 Correct 515 ms 112288 KB Output is correct
38 Correct 535 ms 112780 KB Output is correct
39 Correct 415 ms 110904 KB Output is correct
40 Correct 455 ms 111784 KB Output is correct
41 Correct 426 ms 73652 KB Output is correct
42 Correct 452 ms 69532 KB Output is correct
43 Correct 105 ms 31156 KB Output is correct
44 Correct 477 ms 74140 KB Output is correct
45 Correct 413 ms 77736 KB Output is correct
46 Correct 364 ms 77504 KB Output is correct
47 Correct 215 ms 67512 KB Output is correct
48 Correct 216 ms 68764 KB Output is correct
49 Correct 254 ms 72344 KB Output is correct
50 Correct 272 ms 69304 KB Output is correct
51 Correct 275 ms 74936 KB Output is correct
52 Correct 2661 ms 207740 KB Output is correct
53 Correct 1588 ms 228588 KB Output is correct
54 Correct 795 ms 123560 KB Output is correct
55 Correct 2673 ms 195780 KB Output is correct
56 Correct 1595 ms 228008 KB Output is correct
57 Correct 1429 ms 228512 KB Output is correct
58 Correct 746 ms 123560 KB Output is correct
59 Correct 2622 ms 195868 KB Output is correct
60 Correct 2759 ms 214696 KB Output is correct
61 Correct 1965 ms 227184 KB Output is correct
62 Correct 1427 ms 222620 KB Output is correct
63 Correct 1668 ms 228464 KB Output is correct
64 Correct 4854 ms 301920 KB Output is correct
65 Correct 2210 ms 69368 KB Output is correct
66 Correct 4463 ms 326472 KB Output is correct
67 Correct 1108 ms 135244 KB Output is correct
68 Correct 4120 ms 241988 KB Output is correct
69 Correct 3646 ms 220928 KB Output is correct
70 Correct 3641 ms 325664 KB Output is correct
71 Correct 4038 ms 326416 KB Output is correct
72 Correct 1147 ms 136624 KB Output is correct
73 Correct 3892 ms 234928 KB Output is correct
74 Correct 4410 ms 297800 KB Output is correct
75 Execution timed out 5024 ms 325028 KB Time limit exceeded
76 Halted 0 ms 0 KB -