oj.uz

Submission #1100422

# Submission time Handle Problem Language Result Execution time Memory
1100422 2024-10-13T19:35:40 Z vladilius New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 409964 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> s1[N], s2[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 add(int v, int tl, int tr, int p, int x, bool t){
        if (tl == tr){
            if (t){
                s2[all[v].i].insert(x);
                all[v].m2 = max(all[v].m2, x);
            }
            else{
                s1[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);
            add(all[v].l, tl, tm, p, x, t);
        }
        else {
            if (!all[v].r) all[v].r = nw(tm + 1, tr);
            add(all[v].r, tm + 1, tr, p, x, t);
        }
        recalc(v);
    }
    void add(int l, int r){
        if (l == 1){
            add(1, 1, inf, l, r + 1, 1);
            return;
        }
        if (r == inf){
            add(1, 1, inf, inf, l - 1, 0);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) add(1, 1, inf, m, l - 1, 0);
        if (m < r) add(1, 1, inf, m + 1, r + 1, 1);
    }
    void rem(int v, int tl, int tr, int p, int x, bool t){
        if (tl == tr){
            if (t){
                s2[all[v].i].erase(s2[all[v].i].find(x));
                all[v].m2 = s2[all[v].i].empty() ? 0 : *prev(s2[all[v].i].end());
            }
            else{
                s1[all[v].i].erase(s1[all[v].i].find(x));
                all[v].m1 = s1[all[v].i].empty() ? inff : *s1[all[v].i].begin();
            }
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            rem(all[v].l, tl, tm, p, x, t);
        }
        else {
            rem(all[v].r, tm + 1, tr, p, x, t);
        }
        recalc(v);
    }
    void rem(int l, int r){
        if (l == 1){
            rem(1, 1, inf, l, r + 1, 1);
            return;
        }
        if (r == inf){
            rem(1, 1, inf, inf, l - 1, 0);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) rem(1, 1, inf, m, l - 1, 0);
        if (m < r) rem(1, 1, inf, m + 1, r + 1, 1);
    }
    int get(int v, int tl, int tr, int l, int r, bool t){
        if (l > tr || r < tl) return inff * !t;
        if (l <= tl && tr <= r) return (t) ? all[v].m2 : all[v].m1;
        int tm = (tl + tr) / 2, out = inff * !t;
        if (all[v].l){
            if (t){
                out = max(out, get(all[v].l, tl, tm, l, r, t));
            }
            else {
                out = min(out, get(all[v].l, tl, tm, l, r, t));
            }
        }
        if (all[v].r){
            if (t){
                out = max(out, get(all[v].r, tm + 1, tr, l, r, t));
            }
            else {
                out = min(out, get(all[v].r, tm + 1, tr, l, r, t));
            }
        }
        return out;
    }
    pii get(int x){
        return {get(1, 1, inf, x, inf, 0), get(1, 1, inf, 1, x, 1)};
    }
};
 
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 196 ms 188232 KB Output is correct
2 Correct 182 ms 188072 KB Output is correct
3 Correct 186 ms 188380 KB Output is correct
4 Correct 189 ms 188152 KB Output is correct
5 Correct 185 ms 188232 KB Output is correct
6 Correct 188 ms 189080 KB Output is correct
7 Correct 184 ms 188152 KB Output is correct
8 Correct 187 ms 188732 KB Output is correct
9 Correct 172 ms 188304 KB Output is correct
10 Correct 175 ms 189080 KB Output is correct
11 Correct 173 ms 188516 KB Output is correct
12 Correct 184 ms 188732 KB Output is correct
13 Correct 169 ms 188364 KB Output is correct
14 Correct 175 ms 188524 KB Output is correct
15 Correct 168 ms 188488 KB Output is correct
16 Correct 181 ms 188488 KB Output is correct
17 Correct 192 ms 188720 KB Output is correct
18 Correct 192 ms 188488 KB Output is correct
19 Correct 189 ms 188488 KB Output is correct
20 Correct 188 ms 188728 KB Output is correct
21 Correct 192 ms 188232 KB Output is correct
22 Correct 186 ms 188404 KB Output is correct
23 Correct 177 ms 188488 KB Output is correct
24 Correct 170 ms 188488 KB Output is correct
25 Correct 206 ms 188728 KB Output is correct
26 Correct 190 ms 188732 KB Output is correct
27 Correct 189 ms 188232 KB Output is correct
28 Correct 183 ms 188452 KB Output is correct
29 Correct 187 ms 188488 KB Output is correct
30 Correct 201 ms 188488 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 188232 KB Output is correct
2 Correct 182 ms 188072 KB Output is correct
3 Correct 186 ms 188380 KB Output is correct
4 Correct 189 ms 188152 KB Output is correct
5 Correct 185 ms 188232 KB Output is correct
6 Correct 188 ms 189080 KB Output is correct
7 Correct 184 ms 188152 KB Output is correct
8 Correct 187 ms 188732 KB Output is correct
9 Correct 172 ms 188304 KB Output is correct
10 Correct 175 ms 189080 KB Output is correct
11 Correct 173 ms 188516 KB Output is correct
12 Correct 184 ms 188732 KB Output is correct
13 Correct 169 ms 188364 KB Output is correct
14 Correct 175 ms 188524 KB Output is correct
15 Correct 168 ms 188488 KB Output is correct
16 Correct 181 ms 188488 KB Output is correct
17 Correct 192 ms 188720 KB Output is correct
18 Correct 192 ms 188488 KB Output is correct
19 Correct 189 ms 188488 KB Output is correct
20 Correct 188 ms 188728 KB Output is correct
21 Correct 192 ms 188232 KB Output is correct
22 Correct 186 ms 188404 KB Output is correct
23 Correct 177 ms 188488 KB Output is correct
24 Correct 170 ms 188488 KB Output is correct
25 Correct 206 ms 188728 KB Output is correct
26 Correct 190 ms 188732 KB Output is correct
27 Correct 189 ms 188232 KB Output is correct
28 Correct 183 ms 188452 KB Output is correct
29 Correct 187 ms 188488 KB Output is correct
30 Correct 201 ms 188488 KB Output is correct
31 Correct 694 ms 241848 KB Output is correct
32 Correct 444 ms 193464 KB Output is correct
33 Correct 682 ms 238184 KB Output is correct
34 Correct 621 ms 238232 KB Output is correct
35 Correct 693 ms 241984 KB Output is correct
36 Correct 748 ms 284580 KB Output is correct
37 Correct 541 ms 237628 KB Output is correct
38 Correct 564 ms 237724 KB Output is correct
39 Correct 495 ms 237564 KB Output is correct
40 Correct 539 ms 237728 KB Output is correct
41 Correct 463 ms 237724 KB Output is correct
42 Correct 439 ms 237716 KB Output is correct
43 Correct 223 ms 194532 KB Output is correct
44 Correct 470 ms 237732 KB Output is correct
45 Correct 446 ms 237732 KB Output is correct
46 Correct 440 ms 237692 KB Output is correct
47 Correct 384 ms 216996 KB Output is correct
48 Correct 382 ms 216924 KB Output is correct
49 Correct 416 ms 216996 KB Output is correct
50 Correct 400 ms 217252 KB Output is correct
51 Correct 410 ms 216996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1674 ms 328732 KB Output is correct
2 Correct 1838 ms 397096 KB Output is correct
3 Correct 910 ms 264780 KB Output is correct
4 Correct 1484 ms 327012 KB Output is correct
5 Correct 1911 ms 397224 KB Output is correct
6 Correct 1963 ms 397112 KB Output is correct
7 Correct 853 ms 264876 KB Output is correct
8 Correct 1134 ms 324460 KB Output is correct
9 Correct 1254 ms 409964 KB Output is correct
10 Correct 1633 ms 397688 KB Output is correct
11 Correct 1316 ms 398728 KB Output is correct
12 Correct 1318 ms 399456 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3619 ms 405540 KB Output is correct
2 Execution timed out 5065 ms 222884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 188232 KB Output is correct
2 Correct 182 ms 188072 KB Output is correct
3 Correct 186 ms 188380 KB Output is correct
4 Correct 189 ms 188152 KB Output is correct
5 Correct 185 ms 188232 KB Output is correct
6 Correct 188 ms 189080 KB Output is correct
7 Correct 184 ms 188152 KB Output is correct
8 Correct 187 ms 188732 KB Output is correct
9 Correct 172 ms 188304 KB Output is correct
10 Correct 175 ms 189080 KB Output is correct
11 Correct 173 ms 188516 KB Output is correct
12 Correct 184 ms 188732 KB Output is correct
13 Correct 169 ms 188364 KB Output is correct
14 Correct 175 ms 188524 KB Output is correct
15 Correct 168 ms 188488 KB Output is correct
16 Correct 181 ms 188488 KB Output is correct
17 Correct 192 ms 188720 KB Output is correct
18 Correct 192 ms 188488 KB Output is correct
19 Correct 189 ms 188488 KB Output is correct
20 Correct 188 ms 188728 KB Output is correct
21 Correct 192 ms 188232 KB Output is correct
22 Correct 186 ms 188404 KB Output is correct
23 Correct 177 ms 188488 KB Output is correct
24 Correct 170 ms 188488 KB Output is correct
25 Correct 206 ms 188728 KB Output is correct
26 Correct 190 ms 188732 KB Output is correct
27 Correct 189 ms 188232 KB Output is correct
28 Correct 183 ms 188452 KB Output is correct
29 Correct 187 ms 188488 KB Output is correct
30 Correct 201 ms 188488 KB Output is correct
31 Correct 694 ms 241848 KB Output is correct
32 Correct 444 ms 193464 KB Output is correct
33 Correct 682 ms 238184 KB Output is correct
34 Correct 621 ms 238232 KB Output is correct
35 Correct 693 ms 241984 KB Output is correct
36 Correct 748 ms 284580 KB Output is correct
37 Correct 541 ms 237628 KB Output is correct
38 Correct 564 ms 237724 KB Output is correct
39 Correct 495 ms 237564 KB Output is correct
40 Correct 539 ms 237728 KB Output is correct
41 Correct 463 ms 237724 KB Output is correct
42 Correct 439 ms 237716 KB Output is correct
43 Correct 223 ms 194532 KB Output is correct
44 Correct 470 ms 237732 KB Output is correct
45 Correct 446 ms 237732 KB Output is correct
46 Correct 440 ms 237692 KB Output is correct
47 Correct 384 ms 216996 KB Output is correct
48 Correct 382 ms 216924 KB Output is correct
49 Correct 416 ms 216996 KB Output is correct
50 Correct 400 ms 217252 KB Output is correct
51 Correct 410 ms 216996 KB Output is correct
52 Correct 353 ms 203704 KB Output is correct
53 Correct 320 ms 198328 KB Output is correct
54 Correct 500 ms 222372 KB Output is correct
55 Correct 440 ms 220892 KB Output is correct
56 Correct 410 ms 222884 KB Output is correct
57 Correct 466 ms 218388 KB Output is correct
58 Correct 433 ms 218532 KB Output is correct
59 Correct 399 ms 220324 KB Output is correct
60 Correct 437 ms 217508 KB Output is correct
61 Correct 254 ms 200380 KB Output is correct
62 Correct 346 ms 203656 KB Output is correct
63 Correct 439 ms 211376 KB Output is correct
64 Correct 447 ms 221084 KB Output is correct
65 Correct 487 ms 218276 KB Output is correct
66 Correct 453 ms 217260 KB Output is correct
67 Correct 421 ms 194544 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 188232 KB Output is correct
2 Correct 182 ms 188072 KB Output is correct
3 Correct 186 ms 188380 KB Output is correct
4 Correct 189 ms 188152 KB Output is correct
5 Correct 185 ms 188232 KB Output is correct
6 Correct 188 ms 189080 KB Output is correct
7 Correct 184 ms 188152 KB Output is correct
8 Correct 187 ms 188732 KB Output is correct
9 Correct 172 ms 188304 KB Output is correct
10 Correct 175 ms 189080 KB Output is correct
11 Correct 173 ms 188516 KB Output is correct
12 Correct 184 ms 188732 KB Output is correct
13 Correct 169 ms 188364 KB Output is correct
14 Correct 175 ms 188524 KB Output is correct
15 Correct 168 ms 188488 KB Output is correct
16 Correct 181 ms 188488 KB Output is correct
17 Correct 192 ms 188720 KB Output is correct
18 Correct 192 ms 188488 KB Output is correct
19 Correct 189 ms 188488 KB Output is correct
20 Correct 188 ms 188728 KB Output is correct
21 Correct 192 ms 188232 KB Output is correct
22 Correct 186 ms 188404 KB Output is correct
23 Correct 177 ms 188488 KB Output is correct
24 Correct 170 ms 188488 KB Output is correct
25 Correct 206 ms 188728 KB Output is correct
26 Correct 190 ms 188732 KB Output is correct
27 Correct 189 ms 188232 KB Output is correct
28 Correct 183 ms 188452 KB Output is correct
29 Correct 187 ms 188488 KB Output is correct
30 Correct 201 ms 188488 KB Output is correct
31 Correct 694 ms 241848 KB Output is correct
32 Correct 444 ms 193464 KB Output is correct
33 Correct 682 ms 238184 KB Output is correct
34 Correct 621 ms 238232 KB Output is correct
35 Correct 693 ms 241984 KB Output is correct
36 Correct 748 ms 284580 KB Output is correct
37 Correct 541 ms 237628 KB Output is correct
38 Correct 564 ms 237724 KB Output is correct
39 Correct 495 ms 237564 KB Output is correct
40 Correct 539 ms 237728 KB Output is correct
41 Correct 463 ms 237724 KB Output is correct
42 Correct 439 ms 237716 KB Output is correct
43 Correct 223 ms 194532 KB Output is correct
44 Correct 470 ms 237732 KB Output is correct
45 Correct 446 ms 237732 KB Output is correct
46 Correct 440 ms 237692 KB Output is correct
47 Correct 384 ms 216996 KB Output is correct
48 Correct 382 ms 216924 KB Output is correct
49 Correct 416 ms 216996 KB Output is correct
50 Correct 400 ms 217252 KB Output is correct
51 Correct 410 ms 216996 KB Output is correct
52 Correct 1674 ms 328732 KB Output is correct
53 Correct 1838 ms 397096 KB Output is correct
54 Correct 910 ms 264780 KB Output is correct
55 Correct 1484 ms 327012 KB Output is correct
56 Correct 1911 ms 397224 KB Output is correct
57 Correct 1963 ms 397112 KB Output is correct
58 Correct 853 ms 264876 KB Output is correct
59 Correct 1134 ms 324460 KB Output is correct
60 Correct 1254 ms 409964 KB Output is correct
61 Correct 1633 ms 397688 KB Output is correct
62 Correct 1316 ms 398728 KB Output is correct
63 Correct 1318 ms 399456 KB Output is correct
64 Correct 3619 ms 405540 KB Output is correct
65 Execution timed out 5065 ms 222884 KB Time limit exceeded
66 Halted 0 ms 0 KB -