oj.uz

Submission #1100425

# Submission time Handle Problem Language Result Execution time Memory
1100425 2024-10-13T19:52:05 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 recalc(int v){
        all[v].m1 = inff; all[v].m2 = 0;
        if (all[v].l){
            all[v].m1 = min(all[v].m1, all[all[v].l].m1);
            all[v].m2 = max(all[v].m2, all[all[v].l].m2);
        }
        if (all[v].r){
            all[v].m1 = min(all[v].m1, all[all[v].r].m1);
            all[v].m2 = max(all[v].m2, all[all[v].r].m2);
        }
    }
    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);
        }
        recalc(v);
    }
    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);
        }
        recalc(v);
    }
    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);
        }
        recalc(v);
    }
    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);
        }
        recalc(v);
    }
    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);
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
    }
    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});
    }
    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 81 ms 94280 KB Output is correct
2 Correct 77 ms 94280 KB Output is correct
3 Correct 81 ms 94280 KB Output is correct
4 Correct 100 ms 94408 KB Output is correct
5 Correct 94 ms 94272 KB Output is correct
6 Correct 95 ms 95160 KB Output is correct
7 Correct 79 ms 94280 KB Output is correct
8 Correct 85 ms 94788 KB Output is correct
9 Correct 97 ms 94424 KB Output is correct
10 Correct 97 ms 95128 KB Output is correct
11 Correct 94 ms 94556 KB Output is correct
12 Correct 93 ms 94744 KB Output is correct
13 Correct 80 ms 94536 KB Output is correct
14 Correct 83 ms 94540 KB Output is correct
15 Correct 92 ms 94536 KB Output is correct
16 Correct 93 ms 94488 KB Output is correct
17 Correct 84 ms 94768 KB Output is correct
18 Correct 90 ms 94536 KB Output is correct
19 Correct 94 ms 94536 KB Output is correct
20 Correct 93 ms 94796 KB Output is correct
21 Correct 97 ms 94284 KB Output is correct
22 Correct 82 ms 94320 KB Output is correct
23 Correct 88 ms 94536 KB Output is correct
24 Correct 96 ms 94536 KB Output is correct
25 Correct 95 ms 94864 KB Output is correct
26 Correct 96 ms 94724 KB Output is correct
27 Correct 91 ms 94280 KB Output is correct
28 Correct 87 ms 94692 KB Output is correct
29 Correct 80 ms 94536 KB Output is correct
30 Correct 84 ms 94536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 94280 KB Output is correct
2 Correct 77 ms 94280 KB Output is correct
3 Correct 81 ms 94280 KB Output is correct
4 Correct 100 ms 94408 KB Output is correct
5 Correct 94 ms 94272 KB Output is correct
6 Correct 95 ms 95160 KB Output is correct
7 Correct 79 ms 94280 KB Output is correct
8 Correct 85 ms 94788 KB Output is correct
9 Correct 97 ms 94424 KB Output is correct
10 Correct 97 ms 95128 KB Output is correct
11 Correct 94 ms 94556 KB Output is correct
12 Correct 93 ms 94744 KB Output is correct
13 Correct 80 ms 94536 KB Output is correct
14 Correct 83 ms 94540 KB Output is correct
15 Correct 92 ms 94536 KB Output is correct
16 Correct 93 ms 94488 KB Output is correct
17 Correct 84 ms 94768 KB Output is correct
18 Correct 90 ms 94536 KB Output is correct
19 Correct 94 ms 94536 KB Output is correct
20 Correct 93 ms 94796 KB Output is correct
21 Correct 97 ms 94284 KB Output is correct
22 Correct 82 ms 94320 KB Output is correct
23 Correct 88 ms 94536 KB Output is correct
24 Correct 96 ms 94536 KB Output is correct
25 Correct 95 ms 94864 KB Output is correct
26 Correct 96 ms 94724 KB Output is correct
27 Correct 91 ms 94280 KB Output is correct
28 Correct 87 ms 94692 KB Output is correct
29 Correct 80 ms 94536 KB Output is correct
30 Correct 84 ms 94536 KB Output is correct
31 Correct 547 ms 148112 KB Output is correct
32 Correct 333 ms 99576 KB Output is correct
33 Correct 499 ms 144284 KB Output is correct
34 Correct 475 ms 144284 KB Output is correct
35 Correct 587 ms 147904 KB Output is correct
36 Correct 579 ms 190616 KB Output is correct
37 Correct 441 ms 143664 KB Output is correct
38 Correct 467 ms 143772 KB Output is correct
39 Correct 388 ms 143768 KB Output is correct
40 Correct 407 ms 143772 KB Output is correct
41 Correct 374 ms 143772 KB Output is correct
42 Correct 321 ms 143792 KB Output is correct
43 Correct 135 ms 100608 KB Output is correct
44 Correct 345 ms 143788 KB Output is correct
45 Correct 340 ms 143780 KB Output is correct
46 Correct 338 ms 143928 KB Output is correct
47 Correct 276 ms 123044 KB Output is correct
48 Correct 275 ms 122952 KB Output is correct
49 Correct 306 ms 123044 KB Output is correct
50 Correct 316 ms 123304 KB Output is correct
51 Correct 303 ms 123048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 234640 KB Output is correct
2 Correct 1692 ms 303280 KB Output is correct
3 Correct 777 ms 170944 KB Output is correct
4 Correct 1310 ms 233232 KB Output is correct
5 Correct 1734 ms 303248 KB Output is correct
6 Correct 1844 ms 303208 KB Output is correct
7 Correct 751 ms 170840 KB Output is correct
8 Correct 1070 ms 230576 KB Output is correct
9 Correct 1112 ms 315792 KB Output is correct
10 Correct 1411 ms 303504 KB Output is correct
11 Correct 1091 ms 304780 KB Output is correct
12 Correct 1173 ms 305288 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3041 ms 311228 KB Output is correct
2 Execution timed out 5070 ms 128932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 94280 KB Output is correct
2 Correct 77 ms 94280 KB Output is correct
3 Correct 81 ms 94280 KB Output is correct
4 Correct 100 ms 94408 KB Output is correct
5 Correct 94 ms 94272 KB Output is correct
6 Correct 95 ms 95160 KB Output is correct
7 Correct 79 ms 94280 KB Output is correct
8 Correct 85 ms 94788 KB Output is correct
9 Correct 97 ms 94424 KB Output is correct
10 Correct 97 ms 95128 KB Output is correct
11 Correct 94 ms 94556 KB Output is correct
12 Correct 93 ms 94744 KB Output is correct
13 Correct 80 ms 94536 KB Output is correct
14 Correct 83 ms 94540 KB Output is correct
15 Correct 92 ms 94536 KB Output is correct
16 Correct 93 ms 94488 KB Output is correct
17 Correct 84 ms 94768 KB Output is correct
18 Correct 90 ms 94536 KB Output is correct
19 Correct 94 ms 94536 KB Output is correct
20 Correct 93 ms 94796 KB Output is correct
21 Correct 97 ms 94284 KB Output is correct
22 Correct 82 ms 94320 KB Output is correct
23 Correct 88 ms 94536 KB Output is correct
24 Correct 96 ms 94536 KB Output is correct
25 Correct 95 ms 94864 KB Output is correct
26 Correct 96 ms 94724 KB Output is correct
27 Correct 91 ms 94280 KB Output is correct
28 Correct 87 ms 94692 KB Output is correct
29 Correct 80 ms 94536 KB Output is correct
30 Correct 84 ms 94536 KB Output is correct
31 Correct 547 ms 148112 KB Output is correct
32 Correct 333 ms 99576 KB Output is correct
33 Correct 499 ms 144284 KB Output is correct
34 Correct 475 ms 144284 KB Output is correct
35 Correct 587 ms 147904 KB Output is correct
36 Correct 579 ms 190616 KB Output is correct
37 Correct 441 ms 143664 KB Output is correct
38 Correct 467 ms 143772 KB Output is correct
39 Correct 388 ms 143768 KB Output is correct
40 Correct 407 ms 143772 KB Output is correct
41 Correct 374 ms 143772 KB Output is correct
42 Correct 321 ms 143792 KB Output is correct
43 Correct 135 ms 100608 KB Output is correct
44 Correct 345 ms 143788 KB Output is correct
45 Correct 340 ms 143780 KB Output is correct
46 Correct 338 ms 143928 KB Output is correct
47 Correct 276 ms 123044 KB Output is correct
48 Correct 275 ms 122952 KB Output is correct
49 Correct 306 ms 123044 KB Output is correct
50 Correct 316 ms 123304 KB Output is correct
51 Correct 303 ms 123048 KB Output is correct
52 Correct 232 ms 109748 KB Output is correct
53 Correct 248 ms 104448 KB Output is correct
54 Correct 370 ms 128396 KB Output is correct
55 Correct 331 ms 127140 KB Output is correct
56 Correct 318 ms 128932 KB Output is correct
57 Correct 347 ms 124312 KB Output is correct
58 Correct 335 ms 124636 KB Output is correct
59 Correct 320 ms 126484 KB Output is correct
60 Correct 351 ms 123532 KB Output is correct
61 Correct 155 ms 106428 KB Output is correct
62 Correct 228 ms 109748 KB Output is correct
63 Correct 380 ms 117404 KB Output is correct
64 Correct 356 ms 127140 KB Output is correct
65 Correct 374 ms 124324 KB Output is correct
66 Correct 331 ms 123268 KB Output is correct
67 Correct 303 ms 100532 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 94280 KB Output is correct
2 Correct 77 ms 94280 KB Output is correct
3 Correct 81 ms 94280 KB Output is correct
4 Correct 100 ms 94408 KB Output is correct
5 Correct 94 ms 94272 KB Output is correct
6 Correct 95 ms 95160 KB Output is correct
7 Correct 79 ms 94280 KB Output is correct
8 Correct 85 ms 94788 KB Output is correct
9 Correct 97 ms 94424 KB Output is correct
10 Correct 97 ms 95128 KB Output is correct
11 Correct 94 ms 94556 KB Output is correct
12 Correct 93 ms 94744 KB Output is correct
13 Correct 80 ms 94536 KB Output is correct
14 Correct 83 ms 94540 KB Output is correct
15 Correct 92 ms 94536 KB Output is correct
16 Correct 93 ms 94488 KB Output is correct
17 Correct 84 ms 94768 KB Output is correct
18 Correct 90 ms 94536 KB Output is correct
19 Correct 94 ms 94536 KB Output is correct
20 Correct 93 ms 94796 KB Output is correct
21 Correct 97 ms 94284 KB Output is correct
22 Correct 82 ms 94320 KB Output is correct
23 Correct 88 ms 94536 KB Output is correct
24 Correct 96 ms 94536 KB Output is correct
25 Correct 95 ms 94864 KB Output is correct
26 Correct 96 ms 94724 KB Output is correct
27 Correct 91 ms 94280 KB Output is correct
28 Correct 87 ms 94692 KB Output is correct
29 Correct 80 ms 94536 KB Output is correct
30 Correct 84 ms 94536 KB Output is correct
31 Correct 547 ms 148112 KB Output is correct
32 Correct 333 ms 99576 KB Output is correct
33 Correct 499 ms 144284 KB Output is correct
34 Correct 475 ms 144284 KB Output is correct
35 Correct 587 ms 147904 KB Output is correct
36 Correct 579 ms 190616 KB Output is correct
37 Correct 441 ms 143664 KB Output is correct
38 Correct 467 ms 143772 KB Output is correct
39 Correct 388 ms 143768 KB Output is correct
40 Correct 407 ms 143772 KB Output is correct
41 Correct 374 ms 143772 KB Output is correct
42 Correct 321 ms 143792 KB Output is correct
43 Correct 135 ms 100608 KB Output is correct
44 Correct 345 ms 143788 KB Output is correct
45 Correct 340 ms 143780 KB Output is correct
46 Correct 338 ms 143928 KB Output is correct
47 Correct 276 ms 123044 KB Output is correct
48 Correct 275 ms 122952 KB Output is correct
49 Correct 306 ms 123044 KB Output is correct
50 Correct 316 ms 123304 KB Output is correct
51 Correct 303 ms 123048 KB Output is correct
52 Correct 1294 ms 234640 KB Output is correct
53 Correct 1692 ms 303280 KB Output is correct
54 Correct 777 ms 170944 KB Output is correct
55 Correct 1310 ms 233232 KB Output is correct
56 Correct 1734 ms 303248 KB Output is correct
57 Correct 1844 ms 303208 KB Output is correct
58 Correct 751 ms 170840 KB Output is correct
59 Correct 1070 ms 230576 KB Output is correct
60 Correct 1112 ms 315792 KB Output is correct
61 Correct 1411 ms 303504 KB Output is correct
62 Correct 1091 ms 304780 KB Output is correct
63 Correct 1173 ms 305288 KB Output is correct
64 Correct 3041 ms 311228 KB Output is correct
65 Execution timed out 5070 ms 128932 KB Time limit exceeded
66 Halted 0 ms 0 KB -