oj.uz

Submission #1100417

# Submission time Handle Problem Language Result Execution time Memory
1100417 2024-10-13T19:30:26 Z vladilius New Home (APIO18_new_home) C++17
5 / 100
 1068 ms 543876 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 = 1e7;

struct IT{
    struct node{
        int m1, m2, i, l, r;
        node(){
            l = r = 0;
            m1 = inff; m2 = 0;
        }
    };
    multiset<int> s1[N], s2[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 = 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 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;
    }
    pii get(int x){
        return {get1(1, 1, inf, x, inf, 0), get1(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 207 ms 224172 KB Output is correct
2 Correct 225 ms 224336 KB Output is correct
3 Correct 223 ms 224112 KB Output is correct
4 Correct 193 ms 224152 KB Output is correct
5 Correct 195 ms 224328 KB Output is correct
6 Correct 215 ms 224204 KB Output is correct
7 Correct 213 ms 224328 KB Output is correct
8 Correct 211 ms 224312 KB Output is correct
9 Correct 204 ms 224328 KB Output is correct
10 Correct 204 ms 224408 KB Output is correct
11 Correct 210 ms 224328 KB Output is correct
12 Correct 207 ms 224328 KB Output is correct
13 Correct 203 ms 224252 KB Output is correct
14 Correct 213 ms 224312 KB Output is correct
15 Correct 213 ms 224204 KB Output is correct
16 Correct 209 ms 224336 KB Output is correct
17 Correct 210 ms 224336 KB Output is correct
18 Correct 217 ms 224172 KB Output is correct
19 Correct 219 ms 224328 KB Output is correct
20 Correct 215 ms 224328 KB Output is correct
21 Correct 218 ms 224328 KB Output is correct
22 Correct 226 ms 224288 KB Output is correct
23 Correct 210 ms 224328 KB Output is correct
24 Correct 219 ms 224164 KB Output is correct
25 Correct 210 ms 224328 KB Output is correct
26 Correct 201 ms 224328 KB Output is correct
27 Correct 201 ms 224328 KB Output is correct
28 Correct 201 ms 224328 KB Output is correct
29 Correct 205 ms 224332 KB Output is correct
30 Correct 209 ms 224328 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 224172 KB Output is correct
2 Correct 225 ms 224336 KB Output is correct
3 Correct 223 ms 224112 KB Output is correct
4 Correct 193 ms 224152 KB Output is correct
5 Correct 195 ms 224328 KB Output is correct
6 Correct 215 ms 224204 KB Output is correct
7 Correct 213 ms 224328 KB Output is correct
8 Correct 211 ms 224312 KB Output is correct
9 Correct 204 ms 224328 KB Output is correct
10 Correct 204 ms 224408 KB Output is correct
11 Correct 210 ms 224328 KB Output is correct
12 Correct 207 ms 224328 KB Output is correct
13 Correct 203 ms 224252 KB Output is correct
14 Correct 213 ms 224312 KB Output is correct
15 Correct 213 ms 224204 KB Output is correct
16 Correct 209 ms 224336 KB Output is correct
17 Correct 210 ms 224336 KB Output is correct
18 Correct 217 ms 224172 KB Output is correct
19 Correct 219 ms 224328 KB Output is correct
20 Correct 215 ms 224328 KB Output is correct
21 Correct 218 ms 224328 KB Output is correct
22 Correct 226 ms 224288 KB Output is correct
23 Correct 210 ms 224328 KB Output is correct
24 Correct 219 ms 224164 KB Output is correct
25 Correct 210 ms 224328 KB Output is correct
26 Correct 201 ms 224328 KB Output is correct
27 Correct 201 ms 224328 KB Output is correct
28 Correct 201 ms 224328 KB Output is correct
29 Correct 205 ms 224332 KB Output is correct
30 Correct 209 ms 224328 KB Output is correct
31 Runtime error 958 ms 479156 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1068 ms 543876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1018 ms 523940 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 224172 KB Output is correct
2 Correct 225 ms 224336 KB Output is correct
3 Correct 223 ms 224112 KB Output is correct
4 Correct 193 ms 224152 KB Output is correct
5 Correct 195 ms 224328 KB Output is correct
6 Correct 215 ms 224204 KB Output is correct
7 Correct 213 ms 224328 KB Output is correct
8 Correct 211 ms 224312 KB Output is correct
9 Correct 204 ms 224328 KB Output is correct
10 Correct 204 ms 224408 KB Output is correct
11 Correct 210 ms 224328 KB Output is correct
12 Correct 207 ms 224328 KB Output is correct
13 Correct 203 ms 224252 KB Output is correct
14 Correct 213 ms 224312 KB Output is correct
15 Correct 213 ms 224204 KB Output is correct
16 Correct 209 ms 224336 KB Output is correct
17 Correct 210 ms 224336 KB Output is correct
18 Correct 217 ms 224172 KB Output is correct
19 Correct 219 ms 224328 KB Output is correct
20 Correct 215 ms 224328 KB Output is correct
21 Correct 218 ms 224328 KB Output is correct
22 Correct 226 ms 224288 KB Output is correct
23 Correct 210 ms 224328 KB Output is correct
24 Correct 219 ms 224164 KB Output is correct
25 Correct 210 ms 224328 KB Output is correct
26 Correct 201 ms 224328 KB Output is correct
27 Correct 201 ms 224328 KB Output is correct
28 Correct 201 ms 224328 KB Output is correct
29 Correct 205 ms 224332 KB Output is correct
30 Correct 209 ms 224328 KB Output is correct
31 Runtime error 958 ms 479156 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 224172 KB Output is correct
2 Correct 225 ms 224336 KB Output is correct
3 Correct 223 ms 224112 KB Output is correct
4 Correct 193 ms 224152 KB Output is correct
5 Correct 195 ms 224328 KB Output is correct
6 Correct 215 ms 224204 KB Output is correct
7 Correct 213 ms 224328 KB Output is correct
8 Correct 211 ms 224312 KB Output is correct
9 Correct 204 ms 224328 KB Output is correct
10 Correct 204 ms 224408 KB Output is correct
11 Correct 210 ms 224328 KB Output is correct
12 Correct 207 ms 224328 KB Output is correct
13 Correct 203 ms 224252 KB Output is correct
14 Correct 213 ms 224312 KB Output is correct
15 Correct 213 ms 224204 KB Output is correct
16 Correct 209 ms 224336 KB Output is correct
17 Correct 210 ms 224336 KB Output is correct
18 Correct 217 ms 224172 KB Output is correct
19 Correct 219 ms 224328 KB Output is correct
20 Correct 215 ms 224328 KB Output is correct
21 Correct 218 ms 224328 KB Output is correct
22 Correct 226 ms 224288 KB Output is correct
23 Correct 210 ms 224328 KB Output is correct
24 Correct 219 ms 224164 KB Output is correct
25 Correct 210 ms 224328 KB Output is correct
26 Correct 201 ms 224328 KB Output is correct
27 Correct 201 ms 224328 KB Output is correct
28 Correct 201 ms 224328 KB Output is correct
29 Correct 205 ms 224332 KB Output is correct
30 Correct 209 ms 224328 KB Output is correct
31 Runtime error 958 ms 479156 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -