oj.uz

Submission #1107856

# Submission time Handle Problem Language Result Execution time Memory
1107856 2024-11-02T08:28:37 Z mispertion New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 466936 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){
    if(*(--spl[i].end()) == x1){
        lt.zer(0, L, R, i);
        spl[i].erase(spl[i].find(x1));
        if(spl[i].size() > 0)
            lt.add(0, L, R, i, *(--spl[i].end()));
    }else{
        spl[i].erase(spl[i].find(x1));
    }
    if(*(--spr[i].end()) == x2){
        rt.zer(0, L, R, i);
        spr[i].erase(spr[i].find(x2));
        if(spr[i].size() > 0)
            rt.add(0, L, R, i, *(--spr[i].end()));
    }else{
        spr[i].erase(spr[i].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 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 5 ms 25168 KB Output is correct
4 Correct 6 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 9 ms 26584 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 8 ms 25680 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct
10 Correct 9 ms 26564 KB Output is correct
11 Correct 6 ms 25680 KB Output is correct
12 Correct 7 ms 26360 KB Output is correct
13 Correct 6 ms 25424 KB Output is correct
14 Correct 7 ms 25680 KB Output is correct
15 Correct 8 ms 25692 KB Output is correct
16 Correct 6 ms 25680 KB Output is correct
17 Correct 7 ms 25936 KB Output is correct
18 Correct 6 ms 25680 KB Output is correct
19 Correct 6 ms 25692 KB Output is correct
20 Correct 10 ms 25936 KB Output is correct
21 Correct 7 ms 25168 KB Output is correct
22 Correct 6 ms 25336 KB Output is correct
23 Correct 6 ms 25680 KB Output is correct
24 Correct 6 ms 25680 KB Output is correct
25 Correct 7 ms 26092 KB Output is correct
26 Correct 7 ms 25936 KB Output is correct
27 Correct 6 ms 25168 KB Output is correct
28 Correct 7 ms 25680 KB Output is correct
29 Correct 6 ms 25680 KB Output is correct
30 Correct 8 ms 25424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 5 ms 25168 KB Output is correct
4 Correct 6 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 9 ms 26584 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 8 ms 25680 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct
10 Correct 9 ms 26564 KB Output is correct
11 Correct 6 ms 25680 KB Output is correct
12 Correct 7 ms 26360 KB Output is correct
13 Correct 6 ms 25424 KB Output is correct
14 Correct 7 ms 25680 KB Output is correct
15 Correct 8 ms 25692 KB Output is correct
16 Correct 6 ms 25680 KB Output is correct
17 Correct 7 ms 25936 KB Output is correct
18 Correct 6 ms 25680 KB Output is correct
19 Correct 6 ms 25692 KB Output is correct
20 Correct 10 ms 25936 KB Output is correct
21 Correct 7 ms 25168 KB Output is correct
22 Correct 6 ms 25336 KB Output is correct
23 Correct 6 ms 25680 KB Output is correct
24 Correct 6 ms 25680 KB Output is correct
25 Correct 7 ms 26092 KB Output is correct
26 Correct 7 ms 25936 KB Output is correct
27 Correct 6 ms 25168 KB Output is correct
28 Correct 7 ms 25680 KB Output is correct
29 Correct 6 ms 25680 KB Output is correct
30 Correct 8 ms 25424 KB Output is correct
31 Correct 1632 ms 170768 KB Output is correct
32 Correct 101 ms 35524 KB Output is correct
33 Correct 1379 ms 165572 KB Output is correct
34 Correct 1346 ms 153540 KB Output is correct
35 Correct 1361 ms 169876 KB Output is correct
36 Correct 1219 ms 170452 KB Output is correct
37 Correct 1020 ms 165356 KB Output is correct
38 Correct 764 ms 154896 KB Output is correct
39 Correct 599 ms 152496 KB Output is correct
40 Correct 655 ms 160472 KB Output is correct
41 Correct 606 ms 97704 KB Output is correct
42 Correct 563 ms 97424 KB Output is correct
43 Correct 88 ms 35524 KB Output is correct
44 Correct 544 ms 97588 KB Output is correct
45 Correct 524 ms 97560 KB Output is correct
46 Correct 544 ms 97704 KB Output is correct
47 Correct 301 ms 88756 KB Output is correct
48 Correct 298 ms 97456 KB Output is correct
49 Correct 333 ms 97424 KB Output is correct
50 Correct 355 ms 97320 KB Output is correct
51 Correct 355 ms 97576 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3873 ms 314952 KB Output is correct
2 Correct 2129 ms 320524 KB Output is correct
3 Correct 1008 ms 136528 KB Output is correct
4 Correct 3394 ms 312180 KB Output is correct
5 Correct 2033 ms 323616 KB Output is correct
6 Correct 2129 ms 321000 KB Output is correct
7 Correct 988 ms 130208 KB Output is correct
8 Correct 3431 ms 311060 KB Output is correct
9 Correct 3290 ms 318952 KB Output is correct
10 Correct 2476 ms 320516 KB Output is correct
11 Correct 1892 ms 322016 KB Output is correct
12 Correct 2164 ms 322476 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 5 ms 25168 KB Output is correct
4 Correct 6 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 9 ms 26584 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 8 ms 25680 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct
10 Correct 9 ms 26564 KB Output is correct
11 Correct 6 ms 25680 KB Output is correct
12 Correct 7 ms 26360 KB Output is correct
13 Correct 6 ms 25424 KB Output is correct
14 Correct 7 ms 25680 KB Output is correct
15 Correct 8 ms 25692 KB Output is correct
16 Correct 6 ms 25680 KB Output is correct
17 Correct 7 ms 25936 KB Output is correct
18 Correct 6 ms 25680 KB Output is correct
19 Correct 6 ms 25692 KB Output is correct
20 Correct 10 ms 25936 KB Output is correct
21 Correct 7 ms 25168 KB Output is correct
22 Correct 6 ms 25336 KB Output is correct
23 Correct 6 ms 25680 KB Output is correct
24 Correct 6 ms 25680 KB Output is correct
25 Correct 7 ms 26092 KB Output is correct
26 Correct 7 ms 25936 KB Output is correct
27 Correct 6 ms 25168 KB Output is correct
28 Correct 7 ms 25680 KB Output is correct
29 Correct 6 ms 25680 KB Output is correct
30 Correct 8 ms 25424 KB Output is correct
31 Correct 1632 ms 170768 KB Output is correct
32 Correct 101 ms 35524 KB Output is correct
33 Correct 1379 ms 165572 KB Output is correct
34 Correct 1346 ms 153540 KB Output is correct
35 Correct 1361 ms 169876 KB Output is correct
36 Correct 1219 ms 170452 KB Output is correct
37 Correct 1020 ms 165356 KB Output is correct
38 Correct 764 ms 154896 KB Output is correct
39 Correct 599 ms 152496 KB Output is correct
40 Correct 655 ms 160472 KB Output is correct
41 Correct 606 ms 97704 KB Output is correct
42 Correct 563 ms 97424 KB Output is correct
43 Correct 88 ms 35524 KB Output is correct
44 Correct 544 ms 97588 KB Output is correct
45 Correct 524 ms 97560 KB Output is correct
46 Correct 544 ms 97704 KB Output is correct
47 Correct 301 ms 88756 KB Output is correct
48 Correct 298 ms 97456 KB Output is correct
49 Correct 333 ms 97424 KB Output is correct
50 Correct 355 ms 97320 KB Output is correct
51 Correct 355 ms 97576 KB Output is correct
52 Correct 170 ms 45488 KB Output is correct
53 Correct 181 ms 36640 KB Output is correct
54 Correct 740 ms 97200 KB Output is correct
55 Correct 467 ms 95980 KB Output is correct
56 Correct 412 ms 98224 KB Output is correct
57 Correct 573 ms 99112 KB Output is correct
58 Correct 543 ms 92852 KB Output is correct
59 Correct 471 ms 97200 KB Output is correct
60 Correct 618 ms 100904 KB Output is correct
61 Correct 223 ms 46000 KB Output is correct
62 Correct 172 ms 45596 KB Output is correct
63 Correct 480 ms 70668 KB Output is correct
64 Correct 547 ms 95664 KB Output is correct
65 Correct 649 ms 99480 KB Output is correct
66 Correct 541 ms 97704 KB Output is correct
67 Correct 237 ms 36764 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 5 ms 25168 KB Output is correct
4 Correct 6 ms 25168 KB Output is correct
5 Correct 6 ms 25168 KB Output is correct
6 Correct 9 ms 26584 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 8 ms 25680 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct
10 Correct 9 ms 26564 KB Output is correct
11 Correct 6 ms 25680 KB Output is correct
12 Correct 7 ms 26360 KB Output is correct
13 Correct 6 ms 25424 KB Output is correct
14 Correct 7 ms 25680 KB Output is correct
15 Correct 8 ms 25692 KB Output is correct
16 Correct 6 ms 25680 KB Output is correct
17 Correct 7 ms 25936 KB Output is correct
18 Correct 6 ms 25680 KB Output is correct
19 Correct 6 ms 25692 KB Output is correct
20 Correct 10 ms 25936 KB Output is correct
21 Correct 7 ms 25168 KB Output is correct
22 Correct 6 ms 25336 KB Output is correct
23 Correct 6 ms 25680 KB Output is correct
24 Correct 6 ms 25680 KB Output is correct
25 Correct 7 ms 26092 KB Output is correct
26 Correct 7 ms 25936 KB Output is correct
27 Correct 6 ms 25168 KB Output is correct
28 Correct 7 ms 25680 KB Output is correct
29 Correct 6 ms 25680 KB Output is correct
30 Correct 8 ms 25424 KB Output is correct
31 Correct 1632 ms 170768 KB Output is correct
32 Correct 101 ms 35524 KB Output is correct
33 Correct 1379 ms 165572 KB Output is correct
34 Correct 1346 ms 153540 KB Output is correct
35 Correct 1361 ms 169876 KB Output is correct
36 Correct 1219 ms 170452 KB Output is correct
37 Correct 1020 ms 165356 KB Output is correct
38 Correct 764 ms 154896 KB Output is correct
39 Correct 599 ms 152496 KB Output is correct
40 Correct 655 ms 160472 KB Output is correct
41 Correct 606 ms 97704 KB Output is correct
42 Correct 563 ms 97424 KB Output is correct
43 Correct 88 ms 35524 KB Output is correct
44 Correct 544 ms 97588 KB Output is correct
45 Correct 524 ms 97560 KB Output is correct
46 Correct 544 ms 97704 KB Output is correct
47 Correct 301 ms 88756 KB Output is correct
48 Correct 298 ms 97456 KB Output is correct
49 Correct 333 ms 97424 KB Output is correct
50 Correct 355 ms 97320 KB Output is correct
51 Correct 355 ms 97576 KB Output is correct
52 Correct 3873 ms 314952 KB Output is correct
53 Correct 2129 ms 320524 KB Output is correct
54 Correct 1008 ms 136528 KB Output is correct
55 Correct 3394 ms 312180 KB Output is correct
56 Correct 2033 ms 323616 KB Output is correct
57 Correct 2129 ms 321000 KB Output is correct
58 Correct 988 ms 130208 KB Output is correct
59 Correct 3431 ms 311060 KB Output is correct
60 Correct 3290 ms 318952 KB Output is correct
61 Correct 2476 ms 320516 KB Output is correct
62 Correct 1892 ms 322016 KB Output is correct
63 Correct 2164 ms 322476 KB Output is correct
64 Execution timed out 5061 ms 466936 KB Time limit exceeded
65 Halted 0 ms 0 KB -