oj.uz

Submission #1108037

# Submission time Handle Problem Language Result Execution time Memory
1108037 2024-11-02T15:51:11 Z mispertion New Home (APIO18_new_home) C++17
80 / 100
 5000 ms 380228 KB 
#include<bits/stdc++.h>

using namespace std;
#pragma GCC optimize("O1")

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];
unordered_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 7 ms 37200 KB Output is correct
2 Correct 7 ms 37200 KB Output is correct
3 Correct 6 ms 37368 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 8 ms 37356 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 9 ms 37468 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 37456 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 8 ms 37436 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 8 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 8 ms 37488 KB Output is correct
19 Correct 7 ms 37468 KB Output is correct
20 Correct 8 ms 37456 KB Output is correct
21 Correct 8 ms 37456 KB Output is correct
22 Correct 8 ms 37624 KB Output is correct
23 Correct 8 ms 37456 KB Output is correct
24 Correct 8 ms 37456 KB Output is correct
25 Correct 8 ms 37456 KB Output is correct
26 Correct 10 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 5 ms 27308 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37200 KB Output is correct
2 Correct 7 ms 37200 KB Output is correct
3 Correct 6 ms 37368 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 8 ms 37356 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 9 ms 37468 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 37456 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 8 ms 37436 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 8 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 8 ms 37488 KB Output is correct
19 Correct 7 ms 37468 KB Output is correct
20 Correct 8 ms 37456 KB Output is correct
21 Correct 8 ms 37456 KB Output is correct
22 Correct 8 ms 37624 KB Output is correct
23 Correct 8 ms 37456 KB Output is correct
24 Correct 8 ms 37456 KB Output is correct
25 Correct 8 ms 37456 KB Output is correct
26 Correct 10 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 5 ms 27308 KB Output is correct
31 Correct 1031 ms 113052 KB Output is correct
32 Correct 104 ms 42680 KB Output is correct
33 Correct 866 ms 114408 KB Output is correct
34 Correct 789 ms 105400 KB Output is correct
35 Correct 936 ms 118200 KB Output is correct
36 Correct 868 ms 118664 KB Output is correct
37 Correct 578 ms 111108 KB Output is correct
38 Correct 590 ms 110384 KB Output is correct
39 Correct 452 ms 110520 KB Output is correct
40 Correct 499 ms 110520 KB Output is correct
41 Correct 394 ms 74288 KB Output is correct
42 Correct 399 ms 77780 KB Output is correct
43 Correct 79 ms 44732 KB Output is correct
44 Correct 444 ms 76476 KB Output is correct
45 Correct 376 ms 77432 KB Output is correct
46 Correct 382 ms 76448 KB Output is correct
47 Correct 222 ms 67000 KB Output is correct
48 Correct 221 ms 67976 KB Output is correct
49 Correct 274 ms 71352 KB Output is correct
50 Correct 327 ms 68536 KB Output is correct
51 Correct 294 ms 73656 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2426 ms 205736 KB Output is correct
2 Correct 1739 ms 214952 KB Output is correct
3 Correct 896 ms 125580 KB Output is correct
4 Correct 2577 ms 195012 KB Output is correct
5 Correct 1804 ms 224272 KB Output is correct
6 Correct 1706 ms 224596 KB Output is correct
7 Correct 796 ms 130476 KB Output is correct
8 Correct 2165 ms 195008 KB Output is correct
9 Correct 2538 ms 211696 KB Output is correct
10 Correct 2108 ms 223348 KB Output is correct
11 Correct 1609 ms 218788 KB Output is correct
12 Correct 1812 ms 222628 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4078 ms 304316 KB Output is correct
2 Correct 2258 ms 67168 KB Output is correct
3 Correct 4152 ms 311372 KB Output is correct
4 Correct 1141 ms 130688 KB Output is correct
5 Correct 3630 ms 225448 KB Output is correct
6 Correct 3141 ms 206676 KB Output is correct
7 Correct 3872 ms 310936 KB Output is correct
8 Correct 3981 ms 311240 KB Output is correct
9 Correct 1010 ms 125060 KB Output is correct
10 Correct 3316 ms 219300 KB Output is correct
11 Correct 4208 ms 283532 KB Output is correct
12 Correct 3950 ms 309844 KB Output is correct
13 Correct 1944 ms 288868 KB Output is correct
14 Correct 1994 ms 293816 KB Output is correct
15 Correct 2318 ms 298920 KB Output is correct
16 Correct 2559 ms 298460 KB Output is correct
17 Correct 2214 ms 299688 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37200 KB Output is correct
2 Correct 7 ms 37200 KB Output is correct
3 Correct 6 ms 37368 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 8 ms 37356 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 9 ms 37468 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 37456 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 8 ms 37436 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 8 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 8 ms 37488 KB Output is correct
19 Correct 7 ms 37468 KB Output is correct
20 Correct 8 ms 37456 KB Output is correct
21 Correct 8 ms 37456 KB Output is correct
22 Correct 8 ms 37624 KB Output is correct
23 Correct 8 ms 37456 KB Output is correct
24 Correct 8 ms 37456 KB Output is correct
25 Correct 8 ms 37456 KB Output is correct
26 Correct 10 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 5 ms 27308 KB Output is correct
31 Correct 1031 ms 113052 KB Output is correct
32 Correct 104 ms 42680 KB Output is correct
33 Correct 866 ms 114408 KB Output is correct
34 Correct 789 ms 105400 KB Output is correct
35 Correct 936 ms 118200 KB Output is correct
36 Correct 868 ms 118664 KB Output is correct
37 Correct 578 ms 111108 KB Output is correct
38 Correct 590 ms 110384 KB Output is correct
39 Correct 452 ms 110520 KB Output is correct
40 Correct 499 ms 110520 KB Output is correct
41 Correct 394 ms 74288 KB Output is correct
42 Correct 399 ms 77780 KB Output is correct
43 Correct 79 ms 44732 KB Output is correct
44 Correct 444 ms 76476 KB Output is correct
45 Correct 376 ms 77432 KB Output is correct
46 Correct 382 ms 76448 KB Output is correct
47 Correct 222 ms 67000 KB Output is correct
48 Correct 221 ms 67976 KB Output is correct
49 Correct 274 ms 71352 KB Output is correct
50 Correct 327 ms 68536 KB Output is correct
51 Correct 294 ms 73656 KB Output is correct
52 Correct 166 ms 55720 KB Output is correct
53 Correct 162 ms 46776 KB Output is correct
54 Correct 476 ms 75688 KB Output is correct
55 Correct 313 ms 70812 KB Output is correct
56 Correct 282 ms 68280 KB Output is correct
57 Correct 341 ms 70328 KB Output is correct
58 Correct 323 ms 69816 KB Output is correct
59 Correct 301 ms 66980 KB Output is correct
60 Correct 345 ms 69632 KB Output is correct
61 Correct 179 ms 55968 KB Output is correct
62 Correct 176 ms 55736 KB Output is correct
63 Correct 332 ms 65700 KB Output is correct
64 Correct 421 ms 72352 KB Output is correct
65 Correct 399 ms 70824 KB Output is correct
66 Correct 390 ms 74396 KB Output is correct
67 Correct 218 ms 43960 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37200 KB Output is correct
2 Correct 7 ms 37200 KB Output is correct
3 Correct 6 ms 37368 KB Output is correct
4 Correct 6 ms 37200 KB Output is correct
5 Correct 8 ms 37356 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 9 ms 37468 KB Output is correct
8 Correct 8 ms 37456 KB Output is correct
9 Correct 7 ms 37456 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 8 ms 37436 KB Output is correct
12 Correct 9 ms 37456 KB Output is correct
13 Correct 8 ms 37456 KB Output is correct
14 Correct 8 ms 37456 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 7 ms 37456 KB Output is correct
18 Correct 8 ms 37488 KB Output is correct
19 Correct 7 ms 37468 KB Output is correct
20 Correct 8 ms 37456 KB Output is correct
21 Correct 8 ms 37456 KB Output is correct
22 Correct 8 ms 37624 KB Output is correct
23 Correct 8 ms 37456 KB Output is correct
24 Correct 8 ms 37456 KB Output is correct
25 Correct 8 ms 37456 KB Output is correct
26 Correct 10 ms 37456 KB Output is correct
27 Correct 7 ms 37456 KB Output is correct
28 Correct 7 ms 37456 KB Output is correct
29 Correct 7 ms 37456 KB Output is correct
30 Correct 5 ms 27308 KB Output is correct
31 Correct 1031 ms 113052 KB Output is correct
32 Correct 104 ms 42680 KB Output is correct
33 Correct 866 ms 114408 KB Output is correct
34 Correct 789 ms 105400 KB Output is correct
35 Correct 936 ms 118200 KB Output is correct
36 Correct 868 ms 118664 KB Output is correct
37 Correct 578 ms 111108 KB Output is correct
38 Correct 590 ms 110384 KB Output is correct
39 Correct 452 ms 110520 KB Output is correct
40 Correct 499 ms 110520 KB Output is correct
41 Correct 394 ms 74288 KB Output is correct
42 Correct 399 ms 77780 KB Output is correct
43 Correct 79 ms 44732 KB Output is correct
44 Correct 444 ms 76476 KB Output is correct
45 Correct 376 ms 77432 KB Output is correct
46 Correct 382 ms 76448 KB Output is correct
47 Correct 222 ms 67000 KB Output is correct
48 Correct 221 ms 67976 KB Output is correct
49 Correct 274 ms 71352 KB Output is correct
50 Correct 327 ms 68536 KB Output is correct
51 Correct 294 ms 73656 KB Output is correct
52 Correct 2426 ms 205736 KB Output is correct
53 Correct 1739 ms 214952 KB Output is correct
54 Correct 896 ms 125580 KB Output is correct
55 Correct 2577 ms 195012 KB Output is correct
56 Correct 1804 ms 224272 KB Output is correct
57 Correct 1706 ms 224596 KB Output is correct
58 Correct 796 ms 130476 KB Output is correct
59 Correct 2165 ms 195008 KB Output is correct
60 Correct 2538 ms 211696 KB Output is correct
61 Correct 2108 ms 223348 KB Output is correct
62 Correct 1609 ms 218788 KB Output is correct
63 Correct 1812 ms 222628 KB Output is correct
64 Correct 4078 ms 304316 KB Output is correct
65 Correct 2258 ms 67168 KB Output is correct
66 Correct 4152 ms 311372 KB Output is correct
67 Correct 1141 ms 130688 KB Output is correct
68 Correct 3630 ms 225448 KB Output is correct
69 Correct 3141 ms 206676 KB Output is correct
70 Correct 3872 ms 310936 KB Output is correct
71 Correct 3981 ms 311240 KB Output is correct
72 Correct 1010 ms 125060 KB Output is correct
73 Correct 3316 ms 219300 KB Output is correct
74 Correct 4208 ms 283532 KB Output is correct
75 Correct 3950 ms 309844 KB Output is correct
76 Correct 1944 ms 288868 KB Output is correct
77 Correct 1994 ms 293816 KB Output is correct
78 Correct 2318 ms 298920 KB Output is correct
79 Correct 2559 ms 298460 KB Output is correct
80 Correct 2214 ms 299688 KB Output is correct
81 Correct 166 ms 55720 KB Output is correct
82 Correct 162 ms 46776 KB Output is correct
83 Correct 476 ms 75688 KB Output is correct
84 Correct 313 ms 70812 KB Output is correct
85 Correct 282 ms 68280 KB Output is correct
86 Correct 341 ms 70328 KB Output is correct
87 Correct 323 ms 69816 KB Output is correct
88 Correct 301 ms 66980 KB Output is correct
89 Correct 345 ms 69632 KB Output is correct
90 Correct 179 ms 55968 KB Output is correct
91 Correct 176 ms 55736 KB Output is correct
92 Correct 332 ms 65700 KB Output is correct
93 Correct 421 ms 72352 KB Output is correct
94 Correct 399 ms 70824 KB Output is correct
95 Correct 390 ms 74396 KB Output is correct
96 Correct 218 ms 43960 KB Output is correct
97 Correct 1349 ms 123816 KB Output is correct
98 Correct 1616 ms 58768 KB Output is correct
99 Execution timed out 5073 ms 380228 KB Time limit exceeded
100 Halted 0 ms 0 KB -