oj.uz

답안 #1100228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100228 2024-10-13T10:20:17 Z vladilius 새 집 (APIO18_new_home) C++17
57 / 100
 5000 ms 283008 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 171080 KB Output is correct
2 Correct 155 ms 171080 KB Output is correct
3 Correct 159 ms 170940 KB Output is correct
4 Correct 163 ms 170872 KB Output is correct
5 Correct 153 ms 171080 KB Output is correct
6 Correct 180 ms 171080 KB Output is correct
7 Correct 156 ms 171080 KB Output is correct
8 Correct 161 ms 171080 KB Output is correct
9 Correct 146 ms 171080 KB Output is correct
10 Correct 167 ms 171208 KB Output is correct
11 Correct 147 ms 171044 KB Output is correct
12 Correct 150 ms 171216 KB Output is correct
13 Correct 150 ms 171140 KB Output is correct
14 Correct 150 ms 171080 KB Output is correct
15 Correct 147 ms 171080 KB Output is correct
16 Correct 145 ms 171252 KB Output is correct
17 Correct 146 ms 171080 KB Output is correct
18 Correct 153 ms 171180 KB Output is correct
19 Correct 144 ms 171080 KB Output is correct
20 Correct 158 ms 171080 KB Output is correct
21 Correct 163 ms 171080 KB Output is correct
22 Correct 159 ms 171080 KB Output is correct
23 Correct 163 ms 171248 KB Output is correct
24 Correct 162 ms 171080 KB Output is correct
25 Correct 161 ms 171080 KB Output is correct
26 Correct 167 ms 171104 KB Output is correct
27 Correct 154 ms 171080 KB Output is correct
28 Correct 159 ms 171080 KB Output is correct
29 Correct 166 ms 171080 KB Output is correct
30 Correct 169 ms 171068 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 171080 KB Output is correct
2 Correct 155 ms 171080 KB Output is correct
3 Correct 159 ms 170940 KB Output is correct
4 Correct 163 ms 170872 KB Output is correct
5 Correct 153 ms 171080 KB Output is correct
6 Correct 180 ms 171080 KB Output is correct
7 Correct 156 ms 171080 KB Output is correct
8 Correct 161 ms 171080 KB Output is correct
9 Correct 146 ms 171080 KB Output is correct
10 Correct 167 ms 171208 KB Output is correct
11 Correct 147 ms 171044 KB Output is correct
12 Correct 150 ms 171216 KB Output is correct
13 Correct 150 ms 171140 KB Output is correct
14 Correct 150 ms 171080 KB Output is correct
15 Correct 147 ms 171080 KB Output is correct
16 Correct 145 ms 171252 KB Output is correct
17 Correct 146 ms 171080 KB Output is correct
18 Correct 153 ms 171180 KB Output is correct
19 Correct 144 ms 171080 KB Output is correct
20 Correct 158 ms 171080 KB Output is correct
21 Correct 163 ms 171080 KB Output is correct
22 Correct 159 ms 171080 KB Output is correct
23 Correct 163 ms 171248 KB Output is correct
24 Correct 162 ms 171080 KB Output is correct
25 Correct 161 ms 171080 KB Output is correct
26 Correct 167 ms 171104 KB Output is correct
27 Correct 154 ms 171080 KB Output is correct
28 Correct 159 ms 171080 KB Output is correct
29 Correct 166 ms 171080 KB Output is correct
30 Correct 169 ms 171068 KB Output is correct
31 Correct 762 ms 198384 KB Output is correct
32 Correct 573 ms 175944 KB Output is correct
33 Correct 753 ms 194708 KB Output is correct
34 Correct 711 ms 194992 KB Output is correct
35 Correct 764 ms 198352 KB Output is correct
36 Correct 757 ms 198468 KB Output is correct
37 Correct 634 ms 193232 KB Output is correct
38 Correct 600 ms 193120 KB Output is correct
39 Correct 536 ms 192840 KB Output is correct
40 Correct 557 ms 192840 KB Output is correct
41 Correct 597 ms 192840 KB Output is correct
42 Correct 492 ms 192844 KB Output is correct
43 Correct 414 ms 178896 KB Output is correct
44 Correct 623 ms 193032 KB Output is correct
45 Correct 646 ms 192800 KB Output is correct
46 Correct 596 ms 192968 KB Output is correct
47 Correct 434 ms 191972 KB Output is correct
48 Correct 467 ms 191820 KB Output is correct
49 Correct 503 ms 192328 KB Output is correct
50 Correct 454 ms 192584 KB Output is correct
51 Correct 499 ms 192184 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2907 ms 259268 KB Output is correct
2 Correct 4027 ms 252364 KB Output is correct
3 Correct 2785 ms 282748 KB Output is correct
4 Correct 3079 ms 263276 KB Output is correct
5 Correct 3863 ms 251792 KB Output is correct
6 Correct 3629 ms 252260 KB Output is correct
7 Correct 2858 ms 283008 KB Output is correct
8 Correct 2503 ms 263280 KB Output is correct
9 Correct 2652 ms 256332 KB Output is correct
10 Correct 3364 ms 252912 KB Output is correct
11 Correct 2169 ms 252064 KB Output is correct
12 Correct 2311 ms 252796 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4008 ms 280044 KB Output is correct
2 Execution timed out 5078 ms 205096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 171080 KB Output is correct
2 Correct 155 ms 171080 KB Output is correct
3 Correct 159 ms 170940 KB Output is correct
4 Correct 163 ms 170872 KB Output is correct
5 Correct 153 ms 171080 KB Output is correct
6 Correct 180 ms 171080 KB Output is correct
7 Correct 156 ms 171080 KB Output is correct
8 Correct 161 ms 171080 KB Output is correct
9 Correct 146 ms 171080 KB Output is correct
10 Correct 167 ms 171208 KB Output is correct
11 Correct 147 ms 171044 KB Output is correct
12 Correct 150 ms 171216 KB Output is correct
13 Correct 150 ms 171140 KB Output is correct
14 Correct 150 ms 171080 KB Output is correct
15 Correct 147 ms 171080 KB Output is correct
16 Correct 145 ms 171252 KB Output is correct
17 Correct 146 ms 171080 KB Output is correct
18 Correct 153 ms 171180 KB Output is correct
19 Correct 144 ms 171080 KB Output is correct
20 Correct 158 ms 171080 KB Output is correct
21 Correct 163 ms 171080 KB Output is correct
22 Correct 159 ms 171080 KB Output is correct
23 Correct 163 ms 171248 KB Output is correct
24 Correct 162 ms 171080 KB Output is correct
25 Correct 161 ms 171080 KB Output is correct
26 Correct 167 ms 171104 KB Output is correct
27 Correct 154 ms 171080 KB Output is correct
28 Correct 159 ms 171080 KB Output is correct
29 Correct 166 ms 171080 KB Output is correct
30 Correct 169 ms 171068 KB Output is correct
31 Correct 762 ms 198384 KB Output is correct
32 Correct 573 ms 175944 KB Output is correct
33 Correct 753 ms 194708 KB Output is correct
34 Correct 711 ms 194992 KB Output is correct
35 Correct 764 ms 198352 KB Output is correct
36 Correct 757 ms 198468 KB Output is correct
37 Correct 634 ms 193232 KB Output is correct
38 Correct 600 ms 193120 KB Output is correct
39 Correct 536 ms 192840 KB Output is correct
40 Correct 557 ms 192840 KB Output is correct
41 Correct 597 ms 192840 KB Output is correct
42 Correct 492 ms 192844 KB Output is correct
43 Correct 414 ms 178896 KB Output is correct
44 Correct 623 ms 193032 KB Output is correct
45 Correct 646 ms 192800 KB Output is correct
46 Correct 596 ms 192968 KB Output is correct
47 Correct 434 ms 191972 KB Output is correct
48 Correct 467 ms 191820 KB Output is correct
49 Correct 503 ms 192328 KB Output is correct
50 Correct 454 ms 192584 KB Output is correct
51 Correct 499 ms 192184 KB Output is correct
52 Correct 447 ms 204104 KB Output is correct
53 Correct 440 ms 198728 KB Output is correct
54 Correct 501 ms 200008 KB Output is correct
55 Correct 646 ms 196680 KB Output is correct
56 Correct 647 ms 198588 KB Output is correct
57 Correct 682 ms 194052 KB Output is correct
58 Correct 603 ms 196588 KB Output is correct
59 Correct 548 ms 198536 KB Output is correct
60 Correct 586 ms 193892 KB Output is correct
61 Correct 440 ms 184676 KB Output is correct
62 Correct 532 ms 204184 KB Output is correct
63 Correct 533 ms 200264 KB Output is correct
64 Correct 560 ms 198472 KB Output is correct
65 Correct 593 ms 194632 KB Output is correct
66 Correct 622 ms 193164 KB Output is correct
67 Correct 411 ms 176712 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 171080 KB Output is correct
2 Correct 155 ms 171080 KB Output is correct
3 Correct 159 ms 170940 KB Output is correct
4 Correct 163 ms 170872 KB Output is correct
5 Correct 153 ms 171080 KB Output is correct
6 Correct 180 ms 171080 KB Output is correct
7 Correct 156 ms 171080 KB Output is correct
8 Correct 161 ms 171080 KB Output is correct
9 Correct 146 ms 171080 KB Output is correct
10 Correct 167 ms 171208 KB Output is correct
11 Correct 147 ms 171044 KB Output is correct
12 Correct 150 ms 171216 KB Output is correct
13 Correct 150 ms 171140 KB Output is correct
14 Correct 150 ms 171080 KB Output is correct
15 Correct 147 ms 171080 KB Output is correct
16 Correct 145 ms 171252 KB Output is correct
17 Correct 146 ms 171080 KB Output is correct
18 Correct 153 ms 171180 KB Output is correct
19 Correct 144 ms 171080 KB Output is correct
20 Correct 158 ms 171080 KB Output is correct
21 Correct 163 ms 171080 KB Output is correct
22 Correct 159 ms 171080 KB Output is correct
23 Correct 163 ms 171248 KB Output is correct
24 Correct 162 ms 171080 KB Output is correct
25 Correct 161 ms 171080 KB Output is correct
26 Correct 167 ms 171104 KB Output is correct
27 Correct 154 ms 171080 KB Output is correct
28 Correct 159 ms 171080 KB Output is correct
29 Correct 166 ms 171080 KB Output is correct
30 Correct 169 ms 171068 KB Output is correct
31 Correct 762 ms 198384 KB Output is correct
32 Correct 573 ms 175944 KB Output is correct
33 Correct 753 ms 194708 KB Output is correct
34 Correct 711 ms 194992 KB Output is correct
35 Correct 764 ms 198352 KB Output is correct
36 Correct 757 ms 198468 KB Output is correct
37 Correct 634 ms 193232 KB Output is correct
38 Correct 600 ms 193120 KB Output is correct
39 Correct 536 ms 192840 KB Output is correct
40 Correct 557 ms 192840 KB Output is correct
41 Correct 597 ms 192840 KB Output is correct
42 Correct 492 ms 192844 KB Output is correct
43 Correct 414 ms 178896 KB Output is correct
44 Correct 623 ms 193032 KB Output is correct
45 Correct 646 ms 192800 KB Output is correct
46 Correct 596 ms 192968 KB Output is correct
47 Correct 434 ms 191972 KB Output is correct
48 Correct 467 ms 191820 KB Output is correct
49 Correct 503 ms 192328 KB Output is correct
50 Correct 454 ms 192584 KB Output is correct
51 Correct 499 ms 192184 KB Output is correct
52 Correct 2907 ms 259268 KB Output is correct
53 Correct 4027 ms 252364 KB Output is correct
54 Correct 2785 ms 282748 KB Output is correct
55 Correct 3079 ms 263276 KB Output is correct
56 Correct 3863 ms 251792 KB Output is correct
57 Correct 3629 ms 252260 KB Output is correct
58 Correct 2858 ms 283008 KB Output is correct
59 Correct 2503 ms 263280 KB Output is correct
60 Correct 2652 ms 256332 KB Output is correct
61 Correct 3364 ms 252912 KB Output is correct
62 Correct 2169 ms 252064 KB Output is correct
63 Correct 2311 ms 252796 KB Output is correct
64 Correct 4008 ms 280044 KB Output is correct
65 Execution timed out 5078 ms 205096 KB Time limit exceeded
66 Halted 0 ms 0 KB -