oj.uz

Submission #1107853

# Submission time Handle Problem Language Result Execution time Memory
1107853 2024-11-02T08:23:27 Z mispertion New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 463148 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 = 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;
                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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 4 ms 25168 KB Output is correct
4 Correct 4 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 11 ms 26564 KB Output is correct
7 Correct 6 ms 25168 KB Output is correct
8 Correct 8 ms 25716 KB Output is correct
9 Correct 6 ms 25168 KB Output is correct
10 Correct 8 ms 26564 KB Output is correct
11 Correct 7 ms 25848 KB Output is correct
12 Correct 12 ms 26192 KB Output is correct
13 Correct 7 ms 25424 KB Output is correct
14 Correct 15 ms 25692 KB Output is correct
15 Correct 14 ms 25700 KB Output is correct
16 Correct 14 ms 25576 KB Output is correct
17 Correct 18 ms 25936 KB Output is correct
18 Correct 21 ms 24400 KB Output is correct
19 Correct 19 ms 24400 KB Output is correct
20 Correct 18 ms 24672 KB Output is correct
21 Correct 14 ms 25180 KB Output is correct
22 Correct 16 ms 25424 KB Output is correct
23 Correct 17 ms 24400 KB Output is correct
24 Correct 16 ms 24412 KB Output is correct
25 Correct 19 ms 24656 KB Output is correct
26 Correct 17 ms 25952 KB Output is correct
27 Correct 17 ms 25168 KB Output is correct
28 Correct 14 ms 25680 KB Output is correct
29 Correct 11 ms 25680 KB Output is correct
30 Correct 12 ms 25424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 4 ms 25168 KB Output is correct
4 Correct 4 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 11 ms 26564 KB Output is correct
7 Correct 6 ms 25168 KB Output is correct
8 Correct 8 ms 25716 KB Output is correct
9 Correct 6 ms 25168 KB Output is correct
10 Correct 8 ms 26564 KB Output is correct
11 Correct 7 ms 25848 KB Output is correct
12 Correct 12 ms 26192 KB Output is correct
13 Correct 7 ms 25424 KB Output is correct
14 Correct 15 ms 25692 KB Output is correct
15 Correct 14 ms 25700 KB Output is correct
16 Correct 14 ms 25576 KB Output is correct
17 Correct 18 ms 25936 KB Output is correct
18 Correct 21 ms 24400 KB Output is correct
19 Correct 19 ms 24400 KB Output is correct
20 Correct 18 ms 24672 KB Output is correct
21 Correct 14 ms 25180 KB Output is correct
22 Correct 16 ms 25424 KB Output is correct
23 Correct 17 ms 24400 KB Output is correct
24 Correct 16 ms 24412 KB Output is correct
25 Correct 19 ms 24656 KB Output is correct
26 Correct 17 ms 25952 KB Output is correct
27 Correct 17 ms 25168 KB Output is correct
28 Correct 14 ms 25680 KB Output is correct
29 Correct 11 ms 25680 KB Output is correct
30 Correct 12 ms 25424 KB Output is correct
31 Correct 1490 ms 159016 KB Output is correct
32 Correct 125 ms 34244 KB Output is correct
33 Correct 1379 ms 156676 KB Output is correct
34 Correct 1403 ms 153328 KB Output is correct
35 Correct 1518 ms 166644 KB Output is correct
36 Correct 1468 ms 173160 KB Output is correct
37 Correct 941 ms 157296 KB Output is correct
38 Correct 939 ms 154976 KB Output is correct
39 Correct 616 ms 153176 KB Output is correct
40 Correct 603 ms 155288 KB Output is correct
41 Correct 660 ms 94760 KB Output is correct
42 Correct 706 ms 96284 KB Output is correct
43 Correct 83 ms 35748 KB Output is correct
44 Correct 723 ms 95964 KB Output is correct
45 Correct 709 ms 96020 KB Output is correct
46 Correct 647 ms 94228 KB Output is correct
47 Correct 363 ms 90288 KB Output is correct
48 Correct 362 ms 98892 KB Output is correct
49 Correct 420 ms 98856 KB Output is correct
50 Correct 476 ms 99312 KB Output is correct
51 Correct 466 ms 99096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4070 ms 316788 KB Output is correct
2 Correct 2665 ms 328264 KB Output is correct
3 Correct 1176 ms 129184 KB Output is correct
4 Correct 3687 ms 312048 KB Output is correct
5 Correct 2047 ms 323612 KB Output is correct
6 Correct 2405 ms 325252 KB Output is correct
7 Correct 1162 ms 130460 KB Output is correct
8 Correct 3757 ms 310968 KB Output is correct
9 Correct 3494 ms 319664 KB Output is correct
10 Correct 2623 ms 320588 KB Output is correct
11 Correct 2234 ms 318500 KB Output is correct
12 Correct 2317 ms 319432 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5084 ms 463148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 4 ms 25168 KB Output is correct
4 Correct 4 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 11 ms 26564 KB Output is correct
7 Correct 6 ms 25168 KB Output is correct
8 Correct 8 ms 25716 KB Output is correct
9 Correct 6 ms 25168 KB Output is correct
10 Correct 8 ms 26564 KB Output is correct
11 Correct 7 ms 25848 KB Output is correct
12 Correct 12 ms 26192 KB Output is correct
13 Correct 7 ms 25424 KB Output is correct
14 Correct 15 ms 25692 KB Output is correct
15 Correct 14 ms 25700 KB Output is correct
16 Correct 14 ms 25576 KB Output is correct
17 Correct 18 ms 25936 KB Output is correct
18 Correct 21 ms 24400 KB Output is correct
19 Correct 19 ms 24400 KB Output is correct
20 Correct 18 ms 24672 KB Output is correct
21 Correct 14 ms 25180 KB Output is correct
22 Correct 16 ms 25424 KB Output is correct
23 Correct 17 ms 24400 KB Output is correct
24 Correct 16 ms 24412 KB Output is correct
25 Correct 19 ms 24656 KB Output is correct
26 Correct 17 ms 25952 KB Output is correct
27 Correct 17 ms 25168 KB Output is correct
28 Correct 14 ms 25680 KB Output is correct
29 Correct 11 ms 25680 KB Output is correct
30 Correct 12 ms 25424 KB Output is correct
31 Correct 1490 ms 159016 KB Output is correct
32 Correct 125 ms 34244 KB Output is correct
33 Correct 1379 ms 156676 KB Output is correct
34 Correct 1403 ms 153328 KB Output is correct
35 Correct 1518 ms 166644 KB Output is correct
36 Correct 1468 ms 173160 KB Output is correct
37 Correct 941 ms 157296 KB Output is correct
38 Correct 939 ms 154976 KB Output is correct
39 Correct 616 ms 153176 KB Output is correct
40 Correct 603 ms 155288 KB Output is correct
41 Correct 660 ms 94760 KB Output is correct
42 Correct 706 ms 96284 KB Output is correct
43 Correct 83 ms 35748 KB Output is correct
44 Correct 723 ms 95964 KB Output is correct
45 Correct 709 ms 96020 KB Output is correct
46 Correct 647 ms 94228 KB Output is correct
47 Correct 363 ms 90288 KB Output is correct
48 Correct 362 ms 98892 KB Output is correct
49 Correct 420 ms 98856 KB Output is correct
50 Correct 476 ms 99312 KB Output is correct
51 Correct 466 ms 99096 KB Output is correct
52 Correct 252 ms 45604 KB Output is correct
53 Correct 252 ms 36632 KB Output is correct
54 Correct 724 ms 97076 KB Output is correct
55 Correct 512 ms 93476 KB Output is correct
56 Correct 430 ms 96536 KB Output is correct
57 Correct 582 ms 99184 KB Output is correct
58 Correct 549 ms 92852 KB Output is correct
59 Correct 500 ms 95404 KB Output is correct
60 Correct 693 ms 98308 KB Output is correct
61 Correct 207 ms 46000 KB Output is correct
62 Correct 251 ms 45744 KB Output is correct
63 Correct 607 ms 70684 KB Output is correct
64 Correct 665 ms 95784 KB Output is correct
65 Correct 898 ms 99372 KB Output is correct
66 Correct 671 ms 97828 KB Output is correct
67 Correct 335 ms 35524 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 4 ms 25168 KB Output is correct
4 Correct 4 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 11 ms 26564 KB Output is correct
7 Correct 6 ms 25168 KB Output is correct
8 Correct 8 ms 25716 KB Output is correct
9 Correct 6 ms 25168 KB Output is correct
10 Correct 8 ms 26564 KB Output is correct
11 Correct 7 ms 25848 KB Output is correct
12 Correct 12 ms 26192 KB Output is correct
13 Correct 7 ms 25424 KB Output is correct
14 Correct 15 ms 25692 KB Output is correct
15 Correct 14 ms 25700 KB Output is correct
16 Correct 14 ms 25576 KB Output is correct
17 Correct 18 ms 25936 KB Output is correct
18 Correct 21 ms 24400 KB Output is correct
19 Correct 19 ms 24400 KB Output is correct
20 Correct 18 ms 24672 KB Output is correct
21 Correct 14 ms 25180 KB Output is correct
22 Correct 16 ms 25424 KB Output is correct
23 Correct 17 ms 24400 KB Output is correct
24 Correct 16 ms 24412 KB Output is correct
25 Correct 19 ms 24656 KB Output is correct
26 Correct 17 ms 25952 KB Output is correct
27 Correct 17 ms 25168 KB Output is correct
28 Correct 14 ms 25680 KB Output is correct
29 Correct 11 ms 25680 KB Output is correct
30 Correct 12 ms 25424 KB Output is correct
31 Correct 1490 ms 159016 KB Output is correct
32 Correct 125 ms 34244 KB Output is correct
33 Correct 1379 ms 156676 KB Output is correct
34 Correct 1403 ms 153328 KB Output is correct
35 Correct 1518 ms 166644 KB Output is correct
36 Correct 1468 ms 173160 KB Output is correct
37 Correct 941 ms 157296 KB Output is correct
38 Correct 939 ms 154976 KB Output is correct
39 Correct 616 ms 153176 KB Output is correct
40 Correct 603 ms 155288 KB Output is correct
41 Correct 660 ms 94760 KB Output is correct
42 Correct 706 ms 96284 KB Output is correct
43 Correct 83 ms 35748 KB Output is correct
44 Correct 723 ms 95964 KB Output is correct
45 Correct 709 ms 96020 KB Output is correct
46 Correct 647 ms 94228 KB Output is correct
47 Correct 363 ms 90288 KB Output is correct
48 Correct 362 ms 98892 KB Output is correct
49 Correct 420 ms 98856 KB Output is correct
50 Correct 476 ms 99312 KB Output is correct
51 Correct 466 ms 99096 KB Output is correct
52 Correct 4070 ms 316788 KB Output is correct
53 Correct 2665 ms 328264 KB Output is correct
54 Correct 1176 ms 129184 KB Output is correct
55 Correct 3687 ms 312048 KB Output is correct
56 Correct 2047 ms 323612 KB Output is correct
57 Correct 2405 ms 325252 KB Output is correct
58 Correct 1162 ms 130460 KB Output is correct
59 Correct 3757 ms 310968 KB Output is correct
60 Correct 3494 ms 319664 KB Output is correct
61 Correct 2623 ms 320588 KB Output is correct
62 Correct 2234 ms 318500 KB Output is correct
63 Correct 2317 ms 319432 KB Output is correct
64 Execution timed out 5084 ms 463148 KB Time limit exceeded
65 Halted 0 ms 0 KB -