oj.uz

Submission #1100429

# Submission time Handle Problem Language Result Execution time Memory
1100429 2024-10-13T20:37:52 Z vladilius New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 315792 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int inf = 1e8;
const int inff = inf + 1;
const int N = 2e6;

struct IT{
    struct node{
        int m1, m2, i, l, r;
        node(){
            l = r = 0;
            m1 = inff; m2 = 0;
        }
    };
    multiset<int> s[N];
    vector<node> all;
    int cc, cc1;
    void init(){
        all.pb(node());
        all.pb(node());
        cc = 1; cc1 = 0;
    }
    int nw(int tl, int tr){
        all.pb(node()); cc++;
        if (tl == tr){
            cc1++;
            all[cc].i = cc1;
        }
        return cc;
    }
    void add2(int v, int tl, int tr, int p, int x){
        if (tl == tr){
            s[all[v].i].insert(x);
            all[v].m2 = max(all[v].m2, x);
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            if (!all[v].l) all[v].l = nw(tl, tm);
            add2(all[v].l, tl, tm, p, x);
        }
        else {
            if (!all[v].r) all[v].r = nw(tm + 1, tr);
            add2(all[v].r, tm + 1, tr, p, x);
        }
        all[v].m2 = max(all[v].m2, x);
    }
    void add1(int v, int tl, int tr, int p, int x){
        if (tl == tr){
            s[all[v].i].insert(x);
            all[v].m1 = min(all[v].m1, x);
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            if (!all[v].l) all[v].l = nw(tl, tm);
            add1(all[v].l, tl, tm, p, x);
        }
        else {
            if (!all[v].r) all[v].r = nw(tm + 1, tr);
            add1(all[v].r, tm + 1, tr, p, x);
        }
        all[v].m1 = min(all[v].m1, x);
    }
    void add(int l, int r){
        if (l == 1){
            add2(1, 1, inf, l, r + 1);
            return;
        }
        if (r == inf){
            add1(1, 1, inf, inf, l - 1);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) add1(1, 1, inf, m, l - 1);
        if (m < r) add2(1, 1, inf, m + 1, r + 1);
    }
    void rem2(int v, int tl, int tr, int p, int x, bool t){
        if (tl == tr){
            s[all[v].i].erase(s[all[v].i].find(x));
            all[v].m2 = s[all[v].i].empty() ? 0 : *prev(s[all[v].i].end());
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            rem2(all[v].l, tl, tm, p, x, t);
        }
        else {
            rem2(all[v].r, tm + 1, tr, p, x, t);
        }
        all[v].m2 = 0;
        if (all[v].l) all[v].m2 = max(all[v].m2, all[all[v].l].m2);
        if (all[v].r) all[v].m2 = max(all[v].m2, all[all[v].r].m2);
    }
    void rem1(int v, int tl, int tr, int p, int x, bool t){
        if (tl == tr){
            s[all[v].i].erase(s[all[v].i].find(x));
            all[v].m1 = s[all[v].i].empty() ? inff : *s[all[v].i].begin();
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            rem1(all[v].l, tl, tm, p, x, t);
        }
        else {
            rem1(all[v].r, tm + 1, tr, p, x, t);
        }
        all[v].m1 = inff;
        if (all[v].l) all[v].m1 = min(all[v].m1, all[all[v].l].m1);
        if (all[v].r) all[v].m1 = min(all[v].m1, all[all[v].r].m1);
    }
    void rem(int l, int r){
        if (l == 1){
            rem2(1, 1, inf, l, r + 1, 1);
            return;
        }
        if (r == inf){
            rem1(1, 1, inf, inf, l - 1, 0);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) rem1(1, 1, inf, m, l - 1, 0);
        if (m < r) rem2(1, 1, inf, m + 1, r + 1, 1);
    }
    int get2(int v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return all[v].m2;
        int tm = (tl + tr) / 2, out = 0;
        if (all[v].l){
            out = max(out, get2(all[v].l, tl, tm, l, r));
        }
        if (all[v].r){
            out = max(out, get2(all[v].r, tm + 1, tr, l, r));
        }
        return out;
    }
    int get1(int v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return inff;
        if (l <= tl && tr <= r) return all[v].m1;
        int tm = (tl + tr) / 2, out = inff;
        if (all[v].l){
            out = min(out, get1(all[v].l, tl, tm, l, r));
        }
        if (all[v].r){
            out = min(out, get1(all[v].r, tm + 1, tr, l, r));
        }
        return out;
    }
    pii get(int x){
        return {get1(1, 1, inf, x, inf), get2(1, 1, inf, 1, x)};
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k, q; cin>>n>>k>>q;
    vector<int> x(n + 1), t(n + 1), a(n + 1), b(n + 1);
    bool ind = 1, ind1 = 0;
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
        if (a[i] != 1) ind = 0;
        if (b[i] != inf) ind1 = 1;
    }
    vector<int> xq(q + 1), yq(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>xq[i]>>yq[i];
    }
 
    vector<arr3> mp;
    for (int i = 1; i <= n; i++){
        mp.pb({a[i], 1, i});
        if (b[i] < inf) mp.pb({b[i] + 1, 2, i});
    }
    if (!(n <= 1e5 && ind && ind1)){
        for (int i = 1; i <= q; i++){
            mp.pb({yq[i], i + 2, xq[i]});
        }
    }
    
    auto cmp = [&](arr3 x, arr3 y){
        if (x[0] == y[0]){
            return x[1] < y[1];
        }
        return x[0] < y[0];
    };
    
    sort(mp.begin(), mp.end(), cmp);
    
    vector<int> out(q + 1), cnt(k + 1);
    multiset<int> st[k + 1];
    int df = 0, l, r;
    IT T; T.init();
    for (auto [X, tt, i]: mp){
        if (tt == 1){
            df += !cnt[t[i]];
            cnt[t[i]]++;
            if (cnt[t[i]] == 1){
                if (1 < x[i]) T.add(1, x[i] - 1);
                if (x[i] < inf) T.add(x[i] + 1, inf);
                st[t[i]].insert(x[i]);
                continue;
            }
            if (st[t[i]].find(x[i]) != st[t[i]].end()){
                st[t[i]].insert(x[i]);
                continue;
            }
            
            auto it = st[t[i]].upper_bound(x[i]);
            if (it == st[t[i]].end()) r = inf;
            else r = (*it) - 1;
            if (it == st[t[i]].begin()) l = 1;
            else l = *prev(it) + 1;
            
            if (l <= r) T.rem(l, r);
            if (l < x[i]) T.add(l, x[i] - 1);
            if (x[i] < r) T.add(x[i] + 1, r);
            
            st[t[i]].insert(x[i]);
        }
        else if (tt == 2){
            cnt[t[i]]--;
            df -= !cnt[t[i]];
            
            if (st[t[i]].count(x[i]) > 1){
                st[t[i]].erase(st[t[i]].find(x[i]));
                continue;
            }
            
            auto it = st[t[i]].find(x[i]);
            
            if (it == st[t[i]].begin()) l = 1;
            else l = *prev(it) + 1;
            if (it == prev(st[t[i]].end())) r = inf;
            else r = *next(it) - 1;
            
            if (l < x[i]) T.rem(l, x[i] - 1);
            if (x[i] < r) T.rem(x[i] + 1, r);
            
            if (cnt[t[i]]) T.add(l, r);
            st[t[i]].erase(it);
        }
        else {
            int ii = tt - 2;
            if (df < k){
                out[ii] = -1;
                continue;
            }
            
            auto [l, r] = T.get(i);
            if (l != inff) out[ii] = max(out[ii], i - l);
            if (r != 0) out[ii] = max(out[ii], r - i);
        }
    }
    
    for (int i = 1; i <= q; i++){
        cout<<out[i]<<"\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94280 KB Output is correct
2 Correct 95 ms 94384 KB Output is correct
3 Correct 95 ms 94284 KB Output is correct
4 Correct 87 ms 94280 KB Output is correct
5 Correct 93 ms 94376 KB Output is correct
6 Correct 97 ms 95128 KB Output is correct
7 Correct 95 ms 94280 KB Output is correct
8 Correct 92 ms 94792 KB Output is correct
9 Correct 91 ms 94484 KB Output is correct
10 Correct 93 ms 95000 KB Output is correct
11 Correct 83 ms 94596 KB Output is correct
12 Correct 87 ms 94880 KB Output is correct
13 Correct 91 ms 94544 KB Output is correct
14 Correct 88 ms 94536 KB Output is correct
15 Correct 88 ms 94536 KB Output is correct
16 Correct 93 ms 94596 KB Output is correct
17 Correct 90 ms 94692 KB Output is correct
18 Correct 94 ms 94672 KB Output is correct
19 Correct 91 ms 94536 KB Output is correct
20 Correct 100 ms 94780 KB Output is correct
21 Correct 91 ms 94280 KB Output is correct
22 Correct 88 ms 94288 KB Output is correct
23 Correct 92 ms 94548 KB Output is correct
24 Correct 92 ms 94536 KB Output is correct
25 Correct 93 ms 94768 KB Output is correct
26 Correct 94 ms 94780 KB Output is correct
27 Correct 87 ms 94280 KB Output is correct
28 Correct 94 ms 94536 KB Output is correct
29 Correct 100 ms 94536 KB Output is correct
30 Correct 100 ms 94536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94280 KB Output is correct
2 Correct 95 ms 94384 KB Output is correct
3 Correct 95 ms 94284 KB Output is correct
4 Correct 87 ms 94280 KB Output is correct
5 Correct 93 ms 94376 KB Output is correct
6 Correct 97 ms 95128 KB Output is correct
7 Correct 95 ms 94280 KB Output is correct
8 Correct 92 ms 94792 KB Output is correct
9 Correct 91 ms 94484 KB Output is correct
10 Correct 93 ms 95000 KB Output is correct
11 Correct 83 ms 94596 KB Output is correct
12 Correct 87 ms 94880 KB Output is correct
13 Correct 91 ms 94544 KB Output is correct
14 Correct 88 ms 94536 KB Output is correct
15 Correct 88 ms 94536 KB Output is correct
16 Correct 93 ms 94596 KB Output is correct
17 Correct 90 ms 94692 KB Output is correct
18 Correct 94 ms 94672 KB Output is correct
19 Correct 91 ms 94536 KB Output is correct
20 Correct 100 ms 94780 KB Output is correct
21 Correct 91 ms 94280 KB Output is correct
22 Correct 88 ms 94288 KB Output is correct
23 Correct 92 ms 94548 KB Output is correct
24 Correct 92 ms 94536 KB Output is correct
25 Correct 93 ms 94768 KB Output is correct
26 Correct 94 ms 94780 KB Output is correct
27 Correct 87 ms 94280 KB Output is correct
28 Correct 94 ms 94536 KB Output is correct
29 Correct 100 ms 94536 KB Output is correct
30 Correct 100 ms 94536 KB Output is correct
31 Correct 523 ms 147916 KB Output is correct
32 Correct 348 ms 99612 KB Output is correct
33 Correct 516 ms 144288 KB Output is correct
34 Correct 465 ms 144336 KB Output is correct
35 Correct 552 ms 147912 KB Output is correct
36 Correct 552 ms 190612 KB Output is correct
37 Correct 393 ms 143764 KB Output is correct
38 Correct 427 ms 143632 KB Output is correct
39 Correct 371 ms 143756 KB Output is correct
40 Correct 382 ms 143600 KB Output is correct
41 Correct 328 ms 143776 KB Output is correct
42 Correct 303 ms 143732 KB Output is correct
43 Correct 142 ms 100796 KB Output is correct
44 Correct 304 ms 143708 KB Output is correct
45 Correct 296 ms 143768 KB Output is correct
46 Correct 292 ms 143720 KB Output is correct
47 Correct 234 ms 123048 KB Output is correct
48 Correct 248 ms 123056 KB Output is correct
49 Correct 273 ms 123188 KB Output is correct
50 Correct 271 ms 123300 KB Output is correct
51 Correct 288 ms 123048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1354 ms 234640 KB Output is correct
2 Correct 1670 ms 303300 KB Output is correct
3 Correct 785 ms 170916 KB Output is correct
4 Correct 1216 ms 233240 KB Output is correct
5 Correct 1442 ms 303248 KB Output is correct
6 Correct 1531 ms 303524 KB Output is correct
7 Correct 729 ms 170848 KB Output is correct
8 Correct 1002 ms 230560 KB Output is correct
9 Correct 1078 ms 315792 KB Output is correct
10 Correct 1259 ms 303544 KB Output is correct
11 Correct 1038 ms 304780 KB Output is correct
12 Correct 1044 ms 305292 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2637 ms 311184 KB Output is correct
2 Execution timed out 5072 ms 128916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94280 KB Output is correct
2 Correct 95 ms 94384 KB Output is correct
3 Correct 95 ms 94284 KB Output is correct
4 Correct 87 ms 94280 KB Output is correct
5 Correct 93 ms 94376 KB Output is correct
6 Correct 97 ms 95128 KB Output is correct
7 Correct 95 ms 94280 KB Output is correct
8 Correct 92 ms 94792 KB Output is correct
9 Correct 91 ms 94484 KB Output is correct
10 Correct 93 ms 95000 KB Output is correct
11 Correct 83 ms 94596 KB Output is correct
12 Correct 87 ms 94880 KB Output is correct
13 Correct 91 ms 94544 KB Output is correct
14 Correct 88 ms 94536 KB Output is correct
15 Correct 88 ms 94536 KB Output is correct
16 Correct 93 ms 94596 KB Output is correct
17 Correct 90 ms 94692 KB Output is correct
18 Correct 94 ms 94672 KB Output is correct
19 Correct 91 ms 94536 KB Output is correct
20 Correct 100 ms 94780 KB Output is correct
21 Correct 91 ms 94280 KB Output is correct
22 Correct 88 ms 94288 KB Output is correct
23 Correct 92 ms 94548 KB Output is correct
24 Correct 92 ms 94536 KB Output is correct
25 Correct 93 ms 94768 KB Output is correct
26 Correct 94 ms 94780 KB Output is correct
27 Correct 87 ms 94280 KB Output is correct
28 Correct 94 ms 94536 KB Output is correct
29 Correct 100 ms 94536 KB Output is correct
30 Correct 100 ms 94536 KB Output is correct
31 Correct 523 ms 147916 KB Output is correct
32 Correct 348 ms 99612 KB Output is correct
33 Correct 516 ms 144288 KB Output is correct
34 Correct 465 ms 144336 KB Output is correct
35 Correct 552 ms 147912 KB Output is correct
36 Correct 552 ms 190612 KB Output is correct
37 Correct 393 ms 143764 KB Output is correct
38 Correct 427 ms 143632 KB Output is correct
39 Correct 371 ms 143756 KB Output is correct
40 Correct 382 ms 143600 KB Output is correct
41 Correct 328 ms 143776 KB Output is correct
42 Correct 303 ms 143732 KB Output is correct
43 Correct 142 ms 100796 KB Output is correct
44 Correct 304 ms 143708 KB Output is correct
45 Correct 296 ms 143768 KB Output is correct
46 Correct 292 ms 143720 KB Output is correct
47 Correct 234 ms 123048 KB Output is correct
48 Correct 248 ms 123056 KB Output is correct
49 Correct 273 ms 123188 KB Output is correct
50 Correct 271 ms 123300 KB Output is correct
51 Correct 288 ms 123048 KB Output is correct
52 Correct 239 ms 109920 KB Output is correct
53 Correct 225 ms 104324 KB Output is correct
54 Correct 348 ms 128424 KB Output is correct
55 Correct 317 ms 127140 KB Output is correct
56 Correct 327 ms 128856 KB Output is correct
57 Correct 326 ms 124580 KB Output is correct
58 Correct 309 ms 124576 KB Output is correct
59 Correct 304 ms 126380 KB Output is correct
60 Correct 315 ms 123556 KB Output is correct
61 Correct 139 ms 106644 KB Output is correct
62 Correct 237 ms 109748 KB Output is correct
63 Correct 306 ms 117420 KB Output is correct
64 Correct 341 ms 127144 KB Output is correct
65 Correct 354 ms 124308 KB Output is correct
66 Correct 326 ms 123300 KB Output is correct
67 Correct 316 ms 100644 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94280 KB Output is correct
2 Correct 95 ms 94384 KB Output is correct
3 Correct 95 ms 94284 KB Output is correct
4 Correct 87 ms 94280 KB Output is correct
5 Correct 93 ms 94376 KB Output is correct
6 Correct 97 ms 95128 KB Output is correct
7 Correct 95 ms 94280 KB Output is correct
8 Correct 92 ms 94792 KB Output is correct
9 Correct 91 ms 94484 KB Output is correct
10 Correct 93 ms 95000 KB Output is correct
11 Correct 83 ms 94596 KB Output is correct
12 Correct 87 ms 94880 KB Output is correct
13 Correct 91 ms 94544 KB Output is correct
14 Correct 88 ms 94536 KB Output is correct
15 Correct 88 ms 94536 KB Output is correct
16 Correct 93 ms 94596 KB Output is correct
17 Correct 90 ms 94692 KB Output is correct
18 Correct 94 ms 94672 KB Output is correct
19 Correct 91 ms 94536 KB Output is correct
20 Correct 100 ms 94780 KB Output is correct
21 Correct 91 ms 94280 KB Output is correct
22 Correct 88 ms 94288 KB Output is correct
23 Correct 92 ms 94548 KB Output is correct
24 Correct 92 ms 94536 KB Output is correct
25 Correct 93 ms 94768 KB Output is correct
26 Correct 94 ms 94780 KB Output is correct
27 Correct 87 ms 94280 KB Output is correct
28 Correct 94 ms 94536 KB Output is correct
29 Correct 100 ms 94536 KB Output is correct
30 Correct 100 ms 94536 KB Output is correct
31 Correct 523 ms 147916 KB Output is correct
32 Correct 348 ms 99612 KB Output is correct
33 Correct 516 ms 144288 KB Output is correct
34 Correct 465 ms 144336 KB Output is correct
35 Correct 552 ms 147912 KB Output is correct
36 Correct 552 ms 190612 KB Output is correct
37 Correct 393 ms 143764 KB Output is correct
38 Correct 427 ms 143632 KB Output is correct
39 Correct 371 ms 143756 KB Output is correct
40 Correct 382 ms 143600 KB Output is correct
41 Correct 328 ms 143776 KB Output is correct
42 Correct 303 ms 143732 KB Output is correct
43 Correct 142 ms 100796 KB Output is correct
44 Correct 304 ms 143708 KB Output is correct
45 Correct 296 ms 143768 KB Output is correct
46 Correct 292 ms 143720 KB Output is correct
47 Correct 234 ms 123048 KB Output is correct
48 Correct 248 ms 123056 KB Output is correct
49 Correct 273 ms 123188 KB Output is correct
50 Correct 271 ms 123300 KB Output is correct
51 Correct 288 ms 123048 KB Output is correct
52 Correct 1354 ms 234640 KB Output is correct
53 Correct 1670 ms 303300 KB Output is correct
54 Correct 785 ms 170916 KB Output is correct
55 Correct 1216 ms 233240 KB Output is correct
56 Correct 1442 ms 303248 KB Output is correct
57 Correct 1531 ms 303524 KB Output is correct
58 Correct 729 ms 170848 KB Output is correct
59 Correct 1002 ms 230560 KB Output is correct
60 Correct 1078 ms 315792 KB Output is correct
61 Correct 1259 ms 303544 KB Output is correct
62 Correct 1038 ms 304780 KB Output is correct
63 Correct 1044 ms 305292 KB Output is correct
64 Correct 2637 ms 311184 KB Output is correct
65 Execution timed out 5072 ms 128916 KB Time limit exceeded
66 Halted 0 ms 0 KB -