oj.uz

Submission #1100216

# Submission time Handle Problem Language Result Execution time Memory
1100216 2024-10-13T10:02:22 Z vladilius New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 296608 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
const int inf = 1e8;
const int N = 3e5 + 1;
const int NN = 1e7;

struct IT{
    struct node{
        int m, l, r, s;
        node(){
            l = r = m = 0;
        }
    };
    node all[NN];
    multiset<int> st[N];
    int rt, cc, cc1;
    void init(){
        all[1] = node();
        rt = cc = 1;
        cc1 = -1;
    }
    int nw(int tl, int tr){
        all[++cc] = node();
        if (tl == tr){
            st[++cc1] = {};
            all[cc].s = cc1;
        }
        return cc;
    }
    void add(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            st[all[v].s].insert(x);
            all[v].m = max(all[v].m, 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);
        }
        else {
            if (!all[v].r) all[v].r = nw(tm + 1, tr);
            add(all[v].r, tm + 1, tr, p, x);
        }
        all[v].m = 0;
        if (all[v].l) all[v].m = max(all[v].m, all[all[v].l].m);
        if (all[v].r) all[v].m = max(all[v].m, all[all[v].r].m);
    }
    void add(int l, int r){
        add(rt, 1, inf, l, r);
    }
    void rem(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            st[all[v].s].erase(st[all[v].s].find(x));
            all[v].m = (st[all[v].s].empty()) ? 0 : *prev(st[all[v].s].end());
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            rem(all[v].l, tl, tm, p, x);
        }
        else {
            rem(all[v].r, tm + 1, tr, p, x);
        }
        all[v].m = 0;
        if (all[v].l) all[v].m = max(all[v].m, all[all[v].l].m);
        if (all[v].r) all[v].m = max(all[v].m, all[all[v].r].m);
    }
    void rem(int l, int r){
        rem(rt, 1, inf, l, r);
    }
    int get(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].m;
        int tm = (tl + tr) / 2, out = 0;
        if (all[v].l) out = max(out, get(all[v].l, tl, tm, l, r));
        if (all[v].r) out = max(out, get(all[v].r, tm + 1, tr, l, r));
        return out;
    }
    bool get(int l, int r){
        return get(rt, 1, inf, 1, l) >= r;
    }
};

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];
    }

    map<int, vector<pii>> mp;
    for (int i = 1; i <= n; i++){
        mp[a[i]].pb({1, i});
        mp[b[i] + 1].pb({2, i});
    }
    for (int i = 1; i <= q; i++){
        mp[yq[i]].pb({i + 2, xq[i]});
    }
    
    vector<int> out(q + 1), cnt(k + 1);
    multiset<int> st[k + 1];
    int df = 0, l, r;
    vector<pii> qq;
    IT T; T.init();
    for (auto [X, V]: mp){
        qq.clear();
        for (auto [tt, i]: V){
            if (tt == 1){
                df += !cnt[t[i]];
                cnt[t[i]]++;
                if (st[t[i]].empty()){
                    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 {
                qq.pb({tt - 2, i});
            }
        }
        for (auto [ii, x]: qq){
            if (df < k){
                out[ii] = -1;
                continue;
            }
            
            auto check = [&](int d){
                return T.get(max(1, x - d), min(inf, x + d));
            };
            
            int l = 0, r = inf;
            while (l + 1 < r){
                int m = (l + r) / 2;
                if (check(m)){
                    l = m + 1;
                }
                else {
                    r = m;
                }
            }
            if (check(l)) l = r;
            
            out[ii] = l;
        }
    }
    
    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 149 ms 171028 KB Output is correct
2 Correct 153 ms 171092 KB Output is correct
3 Correct 146 ms 170844 KB Output is correct
4 Correct 149 ms 171080 KB Output is correct
5 Correct 156 ms 171056 KB Output is correct
6 Correct 152 ms 171164 KB Output is correct
7 Correct 150 ms 171184 KB Output is correct
8 Correct 148 ms 171080 KB Output is correct
9 Correct 158 ms 171080 KB Output is correct
10 Correct 151 ms 171080 KB Output is correct
11 Correct 178 ms 171080 KB Output is correct
12 Correct 149 ms 171080 KB Output is correct
13 Correct 154 ms 171080 KB Output is correct
14 Correct 155 ms 171156 KB Output is correct
15 Correct 152 ms 171080 KB Output is correct
16 Correct 152 ms 171076 KB Output is correct
17 Correct 158 ms 171136 KB Output is correct
18 Correct 142 ms 171080 KB Output is correct
19 Correct 136 ms 171080 KB Output is correct
20 Correct 138 ms 171080 KB Output is correct
21 Correct 136 ms 171088 KB Output is correct
22 Correct 139 ms 171080 KB Output is correct
23 Correct 136 ms 171260 KB Output is correct
24 Correct 136 ms 171256 KB Output is correct
25 Correct 138 ms 171068 KB Output is correct
26 Correct 145 ms 171080 KB Output is correct
27 Correct 137 ms 171088 KB Output is correct
28 Correct 136 ms 171080 KB Output is correct
29 Correct 140 ms 171080 KB Output is correct
30 Correct 137 ms 170988 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 171028 KB Output is correct
2 Correct 153 ms 171092 KB Output is correct
3 Correct 146 ms 170844 KB Output is correct
4 Correct 149 ms 171080 KB Output is correct
5 Correct 156 ms 171056 KB Output is correct
6 Correct 152 ms 171164 KB Output is correct
7 Correct 150 ms 171184 KB Output is correct
8 Correct 148 ms 171080 KB Output is correct
9 Correct 158 ms 171080 KB Output is correct
10 Correct 151 ms 171080 KB Output is correct
11 Correct 178 ms 171080 KB Output is correct
12 Correct 149 ms 171080 KB Output is correct
13 Correct 154 ms 171080 KB Output is correct
14 Correct 155 ms 171156 KB Output is correct
15 Correct 152 ms 171080 KB Output is correct
16 Correct 152 ms 171076 KB Output is correct
17 Correct 158 ms 171136 KB Output is correct
18 Correct 142 ms 171080 KB Output is correct
19 Correct 136 ms 171080 KB Output is correct
20 Correct 138 ms 171080 KB Output is correct
21 Correct 136 ms 171088 KB Output is correct
22 Correct 139 ms 171080 KB Output is correct
23 Correct 136 ms 171260 KB Output is correct
24 Correct 136 ms 171256 KB Output is correct
25 Correct 138 ms 171068 KB Output is correct
26 Correct 145 ms 171080 KB Output is correct
27 Correct 137 ms 171088 KB Output is correct
28 Correct 136 ms 171080 KB Output is correct
29 Correct 140 ms 171080 KB Output is correct
30 Correct 137 ms 170988 KB Output is correct
31 Correct 744 ms 198504 KB Output is correct
32 Correct 526 ms 175960 KB Output is correct
33 Correct 726 ms 194904 KB Output is correct
34 Correct 783 ms 194904 KB Output is correct
35 Correct 864 ms 198392 KB Output is correct
36 Correct 770 ms 198348 KB Output is correct
37 Correct 679 ms 193220 KB Output is correct
38 Correct 649 ms 193096 KB Output is correct
39 Correct 535 ms 192840 KB Output is correct
40 Correct 549 ms 192788 KB Output is correct
41 Correct 577 ms 192840 KB Output is correct
42 Correct 492 ms 192816 KB Output is correct
43 Correct 353 ms 178992 KB Output is correct
44 Correct 652 ms 192840 KB Output is correct
45 Correct 662 ms 192992 KB Output is correct
46 Correct 597 ms 192844 KB Output is correct
47 Correct 462 ms 192072 KB Output is correct
48 Correct 489 ms 191928 KB Output is correct
49 Correct 496 ms 192328 KB Output is correct
50 Correct 483 ms 192704 KB Output is correct
51 Correct 516 ms 192184 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2825 ms 259228 KB Output is correct
2 Correct 3856 ms 252360 KB Output is correct
3 Correct 2607 ms 296608 KB Output is correct
4 Correct 2888 ms 276964 KB Output is correct
5 Correct 3921 ms 264412 KB Output is correct
6 Correct 3651 ms 264704 KB Output is correct
7 Correct 2730 ms 296600 KB Output is correct
8 Correct 2591 ms 276880 KB Output is correct
9 Correct 2442 ms 269972 KB Output is correct
10 Correct 3201 ms 265840 KB Output is correct
11 Correct 2389 ms 264404 KB Output is correct
12 Correct 2314 ms 265816 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3778 ms 280048 KB Output is correct
2 Execution timed out 5068 ms 205232 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 171028 KB Output is correct
2 Correct 153 ms 171092 KB Output is correct
3 Correct 146 ms 170844 KB Output is correct
4 Correct 149 ms 171080 KB Output is correct
5 Correct 156 ms 171056 KB Output is correct
6 Correct 152 ms 171164 KB Output is correct
7 Correct 150 ms 171184 KB Output is correct
8 Correct 148 ms 171080 KB Output is correct
9 Correct 158 ms 171080 KB Output is correct
10 Correct 151 ms 171080 KB Output is correct
11 Correct 178 ms 171080 KB Output is correct
12 Correct 149 ms 171080 KB Output is correct
13 Correct 154 ms 171080 KB Output is correct
14 Correct 155 ms 171156 KB Output is correct
15 Correct 152 ms 171080 KB Output is correct
16 Correct 152 ms 171076 KB Output is correct
17 Correct 158 ms 171136 KB Output is correct
18 Correct 142 ms 171080 KB Output is correct
19 Correct 136 ms 171080 KB Output is correct
20 Correct 138 ms 171080 KB Output is correct
21 Correct 136 ms 171088 KB Output is correct
22 Correct 139 ms 171080 KB Output is correct
23 Correct 136 ms 171260 KB Output is correct
24 Correct 136 ms 171256 KB Output is correct
25 Correct 138 ms 171068 KB Output is correct
26 Correct 145 ms 171080 KB Output is correct
27 Correct 137 ms 171088 KB Output is correct
28 Correct 136 ms 171080 KB Output is correct
29 Correct 140 ms 171080 KB Output is correct
30 Correct 137 ms 170988 KB Output is correct
31 Correct 744 ms 198504 KB Output is correct
32 Correct 526 ms 175960 KB Output is correct
33 Correct 726 ms 194904 KB Output is correct
34 Correct 783 ms 194904 KB Output is correct
35 Correct 864 ms 198392 KB Output is correct
36 Correct 770 ms 198348 KB Output is correct
37 Correct 679 ms 193220 KB Output is correct
38 Correct 649 ms 193096 KB Output is correct
39 Correct 535 ms 192840 KB Output is correct
40 Correct 549 ms 192788 KB Output is correct
41 Correct 577 ms 192840 KB Output is correct
42 Correct 492 ms 192816 KB Output is correct
43 Correct 353 ms 178992 KB Output is correct
44 Correct 652 ms 192840 KB Output is correct
45 Correct 662 ms 192992 KB Output is correct
46 Correct 597 ms 192844 KB Output is correct
47 Correct 462 ms 192072 KB Output is correct
48 Correct 489 ms 191928 KB Output is correct
49 Correct 496 ms 192328 KB Output is correct
50 Correct 483 ms 192704 KB Output is correct
51 Correct 516 ms 192184 KB Output is correct
52 Correct 405 ms 204104 KB Output is correct
53 Correct 395 ms 198728 KB Output is correct
54 Correct 451 ms 200008 KB Output is correct
55 Correct 610 ms 196776 KB Output is correct
56 Correct 621 ms 198472 KB Output is correct
57 Correct 628 ms 194120 KB Output is correct
58 Correct 579 ms 196680 KB Output is correct
59 Correct 535 ms 198536 KB Output is correct
60 Correct 562 ms 193892 KB Output is correct
61 Correct 371 ms 184676 KB Output is correct
62 Correct 555 ms 204104 KB Output is correct
63 Correct 584 ms 200264 KB Output is correct
64 Correct 572 ms 198472 KB Output is correct
65 Correct 575 ms 194632 KB Output is correct
66 Correct 596 ms 193096 KB Output is correct
67 Correct 356 ms 176712 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 171028 KB Output is correct
2 Correct 153 ms 171092 KB Output is correct
3 Correct 146 ms 170844 KB Output is correct
4 Correct 149 ms 171080 KB Output is correct
5 Correct 156 ms 171056 KB Output is correct
6 Correct 152 ms 171164 KB Output is correct
7 Correct 150 ms 171184 KB Output is correct
8 Correct 148 ms 171080 KB Output is correct
9 Correct 158 ms 171080 KB Output is correct
10 Correct 151 ms 171080 KB Output is correct
11 Correct 178 ms 171080 KB Output is correct
12 Correct 149 ms 171080 KB Output is correct
13 Correct 154 ms 171080 KB Output is correct
14 Correct 155 ms 171156 KB Output is correct
15 Correct 152 ms 171080 KB Output is correct
16 Correct 152 ms 171076 KB Output is correct
17 Correct 158 ms 171136 KB Output is correct
18 Correct 142 ms 171080 KB Output is correct
19 Correct 136 ms 171080 KB Output is correct
20 Correct 138 ms 171080 KB Output is correct
21 Correct 136 ms 171088 KB Output is correct
22 Correct 139 ms 171080 KB Output is correct
23 Correct 136 ms 171260 KB Output is correct
24 Correct 136 ms 171256 KB Output is correct
25 Correct 138 ms 171068 KB Output is correct
26 Correct 145 ms 171080 KB Output is correct
27 Correct 137 ms 171088 KB Output is correct
28 Correct 136 ms 171080 KB Output is correct
29 Correct 140 ms 171080 KB Output is correct
30 Correct 137 ms 170988 KB Output is correct
31 Correct 744 ms 198504 KB Output is correct
32 Correct 526 ms 175960 KB Output is correct
33 Correct 726 ms 194904 KB Output is correct
34 Correct 783 ms 194904 KB Output is correct
35 Correct 864 ms 198392 KB Output is correct
36 Correct 770 ms 198348 KB Output is correct
37 Correct 679 ms 193220 KB Output is correct
38 Correct 649 ms 193096 KB Output is correct
39 Correct 535 ms 192840 KB Output is correct
40 Correct 549 ms 192788 KB Output is correct
41 Correct 577 ms 192840 KB Output is correct
42 Correct 492 ms 192816 KB Output is correct
43 Correct 353 ms 178992 KB Output is correct
44 Correct 652 ms 192840 KB Output is correct
45 Correct 662 ms 192992 KB Output is correct
46 Correct 597 ms 192844 KB Output is correct
47 Correct 462 ms 192072 KB Output is correct
48 Correct 489 ms 191928 KB Output is correct
49 Correct 496 ms 192328 KB Output is correct
50 Correct 483 ms 192704 KB Output is correct
51 Correct 516 ms 192184 KB Output is correct
52 Correct 2825 ms 259228 KB Output is correct
53 Correct 3856 ms 252360 KB Output is correct
54 Correct 2607 ms 296608 KB Output is correct
55 Correct 2888 ms 276964 KB Output is correct
56 Correct 3921 ms 264412 KB Output is correct
57 Correct 3651 ms 264704 KB Output is correct
58 Correct 2730 ms 296600 KB Output is correct
59 Correct 2591 ms 276880 KB Output is correct
60 Correct 2442 ms 269972 KB Output is correct
61 Correct 3201 ms 265840 KB Output is correct
62 Correct 2389 ms 264404 KB Output is correct
63 Correct 2314 ms 265816 KB Output is correct
64 Correct 3778 ms 280048 KB Output is correct
65 Execution timed out 5068 ms 205232 KB Time limit exceeded
66 Halted 0 ms 0 KB -