oj.uz

Submission #1100415

# Submission time Handle Problem Language Result Execution time Memory
1100415 2024-10-13T18:52:18 Z vladilius New Home (APIO18_new_home) C++17
5 / 100
 2471 ms 1048580 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 = 3e5 + 2;
const int NN = 2e7;
 
struct IT{
    struct node{
        int m1, m2, m3, m4, i, l, r;
        node(){
            l = r = 0;
            m1 = m3 = inff; m2 = m4 = 0;
        }
    };
    multiset<int> s1[N], s2[N], s3[N], s4[N];
    node all[NN];
    int cc, cc1;
    void init(){
        cc = 1; cc1 = 0;
    }
    int nw(int tl, int tr){
        cc++;
        if (tl == tr){
            cc1++;
            all[cc].i = cc1;
        }
        return cc;
    }
    void recalc(int v){
        all[v].m1 = all[v].m3 = inff; all[v].m2 = all[v].m4 = 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);
            all[v].m3 = min(all[v].m3, all[all[v].l].m3);
            all[v].m4 = max(all[v].m4, all[all[v].l].m4);
        }
        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);
            all[v].m3 = min(all[v].m3, all[all[v].r].m3);
            all[v].m4 = max(all[v].m4, all[all[v].r].m4);
        }
    }
    void add1(int v, int tl, int tr, int p, int x, bool t){
        if (tl == tr){
            if (t){
                s4[all[v].i].insert(x);
                all[v].m4 = max(all[v].m4, x);
            }
            else{
                s3[all[v].i].insert(x);
                all[v].m3 = min(all[v].m3, 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, t);
        }
        else {
            if (!all[v].r) all[v].r = nw(tm + 1, tr);
            add1(all[v].r, tm + 1, tr, p, x, t);
        }
        recalc(v);
    }
    void add2(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);
            add2(all[v].l, tl, tm, p, x, t);
        }
        else {
            if (!all[v].r) all[v].r = nw(tm + 1, tr);
            add2(all[v].r, tm + 1, tr, p, x, t);
        }
        recalc(v);
    }
    void add(int l, int r){
        if (l == 1){
            add1(1, 1, inf, r, r + 1, 1);
            return;
        }
        if (r == inf){
            add1(1, 1, inf, l, l - 1, 0);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) add2(1, 1, inf, m, l - 1, 0);
        if (m < r) add2(1, 1, inf, m + 1, r + 1, 1);
    }
    void rem1(int v, int tl, int tr, int p, int x, bool t){
        if (tl == tr){
            if (t){
                s4[all[v].i].erase(s4[all[v].i].find(x));
                all[v].m4 = s4[all[v].i].empty() ? 0 : *prev(s4[all[v].i].end());
            }
            else{
                s3[all[v].i].erase(s3[all[v].i].find(x));
                all[v].m3 = s3[all[v].i].empty() ? inff : *s3[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 rem2(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){
            rem2(all[v].l, tl, tm, p, x, t);
        }
        else {
            rem2(all[v].r, tm + 1, tr, p, x, t);
        }
        recalc(v);
    }
    void rem(int l, int r){
        if (l == 1){
            rem1(1, 1, inf, r, r + 1, 1);
            return;
        }
        if (r == inf){
            rem1(1, 1, inf, l, l - 1, 0);
            return;
        }
        int m = (l + r) / 2;
        if (l <= m) rem2(1, 1, inf, m, l - 1, 0);
        if (m < r) rem2(1, 1, inf, m + 1, r + 1, 1);
    }
    int get1(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, get1(all[v].l, tl, tm, l, r, t));
            }
            else {
                out = min(out, get1(all[v].l, tl, tm, l, r, t));
            }
        }
        if (all[v].r){
            if (t){
                out = max(out, get1(all[v].r, tm + 1, tr, l, r, t));
            }
            else {
                out = min(out, get1(all[v].r, tm + 1, tr, l, r, t));
            }
        }
        return out;
    }
    int get2(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].m4 : all[v].m3;
        int tm = (tl + tr) / 2, out = inff * !t;
        if (all[v].l){
            if (t){
                out = max(out, get2(all[v].l, tl, tm, l, r, t));
            }
            else {
                out = min(out, get2(all[v].l, tl, tm, l, r, t));
            }
        }
        if (all[v].r){
            if (t){
                out = max(out, get2(all[v].r, tm + 1, tr, l, r, t));
            }
            else {
                out = min(out, get2(all[v].r, tm + 1, tr, l, r, t));
            }
        }
        return out;
    }
    pii get(int x){
        return {min(get1(1, 1, inf, x, inf, 0), get2(1, 1, inf, 1, x, 0)), max(get1(1, 1, inf, 1, x, 1), get2(1, 1, inf, x, inf, 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 555 ms 604488 KB Output is correct
2 Correct 554 ms 604744 KB Output is correct
3 Correct 496 ms 604492 KB Output is correct
4 Correct 530 ms 604744 KB Output is correct
5 Correct 514 ms 604588 KB Output is correct
6 Correct 513 ms 604744 KB Output is correct
7 Correct 557 ms 604744 KB Output is correct
8 Correct 552 ms 604620 KB Output is correct
9 Correct 551 ms 604748 KB Output is correct
10 Correct 504 ms 604736 KB Output is correct
11 Correct 553 ms 604636 KB Output is correct
12 Correct 546 ms 604744 KB Output is correct
13 Correct 520 ms 604744 KB Output is correct
14 Correct 540 ms 604588 KB Output is correct
15 Correct 554 ms 604744 KB Output is correct
16 Correct 536 ms 604744 KB Output is correct
17 Correct 505 ms 604568 KB Output is correct
18 Correct 493 ms 604828 KB Output is correct
19 Correct 488 ms 604744 KB Output is correct
20 Correct 490 ms 604668 KB Output is correct
21 Correct 515 ms 604744 KB Output is correct
22 Correct 542 ms 604744 KB Output is correct
23 Correct 511 ms 604816 KB Output is correct
24 Correct 519 ms 604744 KB Output is correct
25 Correct 527 ms 604692 KB Output is correct
26 Correct 523 ms 604648 KB Output is correct
27 Correct 507 ms 604780 KB Output is correct
28 Correct 527 ms 604744 KB Output is correct
29 Correct 525 ms 604744 KB Output is correct
30 Correct 541 ms 604624 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 604488 KB Output is correct
2 Correct 554 ms 604744 KB Output is correct
3 Correct 496 ms 604492 KB Output is correct
4 Correct 530 ms 604744 KB Output is correct
5 Correct 514 ms 604588 KB Output is correct
6 Correct 513 ms 604744 KB Output is correct
7 Correct 557 ms 604744 KB Output is correct
8 Correct 552 ms 604620 KB Output is correct
9 Correct 551 ms 604748 KB Output is correct
10 Correct 504 ms 604736 KB Output is correct
11 Correct 553 ms 604636 KB Output is correct
12 Correct 546 ms 604744 KB Output is correct
13 Correct 520 ms 604744 KB Output is correct
14 Correct 540 ms 604588 KB Output is correct
15 Correct 554 ms 604744 KB Output is correct
16 Correct 536 ms 604744 KB Output is correct
17 Correct 505 ms 604568 KB Output is correct
18 Correct 493 ms 604828 KB Output is correct
19 Correct 488 ms 604744 KB Output is correct
20 Correct 490 ms 604668 KB Output is correct
21 Correct 515 ms 604744 KB Output is correct
22 Correct 542 ms 604744 KB Output is correct
23 Correct 511 ms 604816 KB Output is correct
24 Correct 519 ms 604744 KB Output is correct
25 Correct 527 ms 604692 KB Output is correct
26 Correct 523 ms 604648 KB Output is correct
27 Correct 507 ms 604780 KB Output is correct
28 Correct 527 ms 604744 KB Output is correct
29 Correct 525 ms 604744 KB Output is correct
30 Correct 541 ms 604624 KB Output is correct
31 Runtime error 2471 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2249 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 2376 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 604488 KB Output is correct
2 Correct 554 ms 604744 KB Output is correct
3 Correct 496 ms 604492 KB Output is correct
4 Correct 530 ms 604744 KB Output is correct
5 Correct 514 ms 604588 KB Output is correct
6 Correct 513 ms 604744 KB Output is correct
7 Correct 557 ms 604744 KB Output is correct
8 Correct 552 ms 604620 KB Output is correct
9 Correct 551 ms 604748 KB Output is correct
10 Correct 504 ms 604736 KB Output is correct
11 Correct 553 ms 604636 KB Output is correct
12 Correct 546 ms 604744 KB Output is correct
13 Correct 520 ms 604744 KB Output is correct
14 Correct 540 ms 604588 KB Output is correct
15 Correct 554 ms 604744 KB Output is correct
16 Correct 536 ms 604744 KB Output is correct
17 Correct 505 ms 604568 KB Output is correct
18 Correct 493 ms 604828 KB Output is correct
19 Correct 488 ms 604744 KB Output is correct
20 Correct 490 ms 604668 KB Output is correct
21 Correct 515 ms 604744 KB Output is correct
22 Correct 542 ms 604744 KB Output is correct
23 Correct 511 ms 604816 KB Output is correct
24 Correct 519 ms 604744 KB Output is correct
25 Correct 527 ms 604692 KB Output is correct
26 Correct 523 ms 604648 KB Output is correct
27 Correct 507 ms 604780 KB Output is correct
28 Correct 527 ms 604744 KB Output is correct
29 Correct 525 ms 604744 KB Output is correct
30 Correct 541 ms 604624 KB Output is correct
31 Runtime error 2471 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 604488 KB Output is correct
2 Correct 554 ms 604744 KB Output is correct
3 Correct 496 ms 604492 KB Output is correct
4 Correct 530 ms 604744 KB Output is correct
5 Correct 514 ms 604588 KB Output is correct
6 Correct 513 ms 604744 KB Output is correct
7 Correct 557 ms 604744 KB Output is correct
8 Correct 552 ms 604620 KB Output is correct
9 Correct 551 ms 604748 KB Output is correct
10 Correct 504 ms 604736 KB Output is correct
11 Correct 553 ms 604636 KB Output is correct
12 Correct 546 ms 604744 KB Output is correct
13 Correct 520 ms 604744 KB Output is correct
14 Correct 540 ms 604588 KB Output is correct
15 Correct 554 ms 604744 KB Output is correct
16 Correct 536 ms 604744 KB Output is correct
17 Correct 505 ms 604568 KB Output is correct
18 Correct 493 ms 604828 KB Output is correct
19 Correct 488 ms 604744 KB Output is correct
20 Correct 490 ms 604668 KB Output is correct
21 Correct 515 ms 604744 KB Output is correct
22 Correct 542 ms 604744 KB Output is correct
23 Correct 511 ms 604816 KB Output is correct
24 Correct 519 ms 604744 KB Output is correct
25 Correct 527 ms 604692 KB Output is correct
26 Correct 523 ms 604648 KB Output is correct
27 Correct 507 ms 604780 KB Output is correct
28 Correct 527 ms 604744 KB Output is correct
29 Correct 525 ms 604744 KB Output is correct
30 Correct 541 ms 604624 KB Output is correct
31 Runtime error 2471 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -