oj.uz

답안 #1107870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1107870 2024-11-02T08:53:57 Z mispertion 새 집 (APIO18_new_home) C++17
57 / 100
 5000 ms 301940 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define F first
#define S second

const ld PI = 3.1415926535;
const int N = 5e5 + 2;
const int M = 1e7 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) {
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}


ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

struct segtree{
    int t[M], l[M], r[M];
    int cur = 0;

    segtree(){
        t[0] = -infi;
        l[0] = -1;
        r[0] = -1;
    }

    void zer(int v, int tl, int tr, int i){
        if(tl == tr){
            t[v] = -infi;
            //cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
            return;
        }
        int tm = (tl + tr) / 2;
        if(i <= tm){
            if(l[v] == -1){
                l[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            zer(l[v], tl, tm, i);
        }else{
            if(r[v] == -1){
                r[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            zer(r[v], tm + 1, tr, i);
        }
        t[v] = -infi;
        if(l[v] != -1)
            t[v] = max(t[v], t[l[v]]);
        if(r[v] != -1)
            t[v] = max(t[v], t[r[v]]);
    }

    void add(int v, int tl, int tr, int i, int x){
        if(tl == tr){
            t[v] = max(t[v], x);
            //cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
            return;
        }
        int tm = (tl + tr) / 2;
        if(i <= tm){
            if(l[v] == -1){
                l[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            add(l[v], tl, tm, i, x);
        }else{
            if(r[v] == -1){
                r[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            add(r[v], tm + 1, tr, i, x);
        }
        t[v] = -infi;
        if(l[v] != -1)
            t[v] = max(t[v], t[l[v]]);
        if(r[v] != -1)
            t[v] = max(t[v], t[r[v]]);
        //cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
    }

    void sett(int v, int tl, int tr, int i, int x){
        if(tl == tr){
            t[v] = x;
            //cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
            return;
        }
        int tm = (tl + tr) / 2;
        if(i <= tm){
            if(l[v] == -1){
                l[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            sett(l[v], tl, tm, i, x);
        }else{
            if(r[v] == -1){
                r[v] = ++cur;
                t[cur] = -infi;
                l[cur] = -1;
                r[cur] = -1;
            }
            sett(r[v], tm + 1, tr, i, x);
        }
        t[v] = -infi;
        if(l[v] != -1)
            t[v] = max(t[v], t[l[v]]);
        if(r[v] != -1)
            t[v] = max(t[v], t[r[v]]);
        //cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
    }

    int get(int v, int tl, int tr, int lu, int ru){
        if(v == -1)
            return -infi;
        if(tl > ru || lu > tr)
            return -infi;
        if(lu <= tl && tr <= ru)
            return t[v];
        int tm = (tl + tr) / 2;
        return max(get(l[v], tl, tm, lu, ru), get(r[v], tm + 1, tr, lu, ru));
    }
};

int n, q, k, ans[N], L = 0, R = 2e8;
vector<pair<pii, pii>> evs;
multiset<int> cr[N];
map<int, multiset<int>> spl, spr;
segtree lt = segtree(), rt = segtree();

void add(int i, int x1, int x2){
    lt.add(0, L, R, i, x1);
    rt.add(0, L, R, i, x2);
    spl[i].insert(x1);
    spr[i].insert(x2);
}

void rem(int i, int x1, int x2){
    auto da = spl.find(i);
    auto ha = spr.find(i);
    auto ed = (--da->S.end());
    auto hd = (--ha->S.end());
    if(*ed == x1){
        da->S.erase(ed);
        if(da->S.size() > 0){
            lt.sett(0, L, R, i, *(--da->S.end()));
        }else{
            lt.zer(0, L, R, i);
        }
    }else{
        da->S.erase(da->S.find(x1));
    }
    if(*hd == x2){
        ha->S.erase(hd);
        if(ha->S.size() > 0)
            rt.sett(0, L, R, i, *(--ha->S.end()));
        else
            rt.zer(0, L, R, i);
    }else{
        ha->S.erase(ha->S.find(x2));
    }
}

void solve() {
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        int x, tp, a, b;
        cin >> x >> tp >> a >> b;
        x *= 2;
        evs.push_back({{a, 1}, {x, tp}});
        evs.push_back({{b + 1, -1}, {x, tp}});
    }
    for(int i = 1; i <= q; i++){
        int l, y;
        cin >> l >> y;
        l *= 2;
        evs.push_back({{y, 2}, {l, i}});
    }
    sort(evs.begin(), evs.end());
    int cnt = k;
    for(auto ev : evs){
        //cout << ev.F.F << ' ' << ev.F.S << ' ' << ev.S.F << ' ' << ev.S.S << '\n';
        if(ev.F.S == 1){
            int x = ev.S.F, tp = ev.S.S;
            if(cr[tp].find(x) != cr[tp].end()){
                cr[tp].insert(x);
                continue;
            }
            if(cr[tp].size() == 0){
                cr[tp].insert(x);
                add(L, x, x - 2 * L);
                add(R, 2 * R - x, -x);
                cnt--;
                continue;
            }
            int l = -1, r = -1;
            auto it = cr[tp].upper_bound(x);
            if(it != cr[tp].end()){
                add(((*it) + x) / 2, *it, -x);
                r = *it;
            }else{
                add(R, 2 * R - x, -x);
            }
            it = cr[tp].lower_bound(x);
            if(it != cr[tp].begin()){
                it--;
                add((x + (*it)) / 2, x, -(*it));
                l = *it;
            }else{
                add(L, x, x - 2 * L);
            }
            if(l != -1 && r != -1){
                rem((r + l) / 2, r, -l);
            }
            if(r == -1 && l != -1){
                rem(R, 2 * R - l, -l);
            }
            if(r != -1 && l == -1){
                rem(L, r, r - 2 * L);
            }
            cr[tp].insert(x);
        }else if(ev.F.S == -1){
            int x = ev.S.F, tp = ev.S.S;
            int l = -1, r = -1;
            if(cr[tp].count(x) > 1){
                cr[tp].erase(cr[tp].find(x));
                continue;
            }
            auto it = cr[tp].upper_bound(x);
            if(it != cr[tp].end()){
                r = *it;
                rem((r + x) / 2, r, -x);
            }else{
                rem(R, 2 * R - x, -x);
            }
            it = cr[tp].lower_bound(x);
            if(it != cr[tp].begin()){
                it--;
                l = (*it);
                rem((x + l) / 2, x, -l);
            }else{
                rem(L, x, x - 2 * L);
            }
            cr[tp].erase(cr[tp].find(x));
            if(l == -1 && r == -1){
                cnt++;
            }else if(l == -1){
                add(L, r, r - 2 * L);
            }else if(r == -1){
                add(R, 2 * R - l, -l);
            }else{
                add((r + l) / 2, r, -l);
            }
        }else{
            int x = ev.S.F, i = ev.S.S;
            int ret = max(lt.get(0, L, R, L, x) - x, rt.get(0, L, R, x, R) + x);
            if(cnt != 0)
                ans[i] = -1;
            else
                ans[i] = (ret < 0 ? -1 : ret / 2);
        }    
        //cout << cnt << '\n';   
    }
    for(int i = 1; i <=q; i++)
        cout << ans[i] << ' ';
    cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 5 ms 35152 KB Output is correct
4 Correct 6 ms 35152 KB Output is correct
5 Correct 7 ms 35408 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 37456 KB Output is correct
9 Correct 6 ms 35540 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 7 ms 37524 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 8 ms 37456 KB Output is correct
18 Correct 7 ms 37456 KB Output is correct
19 Correct 7 ms 37360 KB Output is correct
20 Correct 7 ms 37456 KB Output is correct
21 Correct 6 ms 35268 KB Output is correct
22 Correct 7 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37456 KB Output is correct
25 Correct 7 ms 37572 KB Output is correct
26 Correct 8 ms 37456 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 8 ms 37456 KB Output is correct
29 Correct 7 ms 37336 KB Output is correct
30 Correct 7 ms 37456 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 5 ms 35152 KB Output is correct
4 Correct 6 ms 35152 KB Output is correct
5 Correct 7 ms 35408 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 37456 KB Output is correct
9 Correct 6 ms 35540 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 7 ms 37524 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 8 ms 37456 KB Output is correct
18 Correct 7 ms 37456 KB Output is correct
19 Correct 7 ms 37360 KB Output is correct
20 Correct 7 ms 37456 KB Output is correct
21 Correct 6 ms 35268 KB Output is correct
22 Correct 7 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37456 KB Output is correct
25 Correct 7 ms 37572 KB Output is correct
26 Correct 8 ms 37456 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 8 ms 37456 KB Output is correct
29 Correct 7 ms 37336 KB Output is correct
30 Correct 7 ms 37456 KB Output is correct
31 Correct 996 ms 119520 KB Output is correct
32 Correct 98 ms 41428 KB Output is correct
33 Correct 821 ms 115384 KB Output is correct
34 Correct 792 ms 113144 KB Output is correct
35 Correct 941 ms 120760 KB Output is correct
36 Correct 993 ms 121260 KB Output is correct
37 Correct 548 ms 112284 KB Output is correct
38 Correct 528 ms 112824 KB Output is correct
39 Correct 439 ms 111016 KB Output is correct
40 Correct 464 ms 111676 KB Output is correct
41 Correct 383 ms 75432 KB Output is correct
42 Correct 401 ms 77496 KB Output is correct
43 Correct 76 ms 42680 KB Output is correct
44 Correct 390 ms 77728 KB Output is correct
45 Correct 387 ms 77756 KB Output is correct
46 Correct 349 ms 77496 KB Output is correct
47 Correct 217 ms 67512 KB Output is correct
48 Correct 274 ms 68796 KB Output is correct
49 Correct 262 ms 72364 KB Output is correct
50 Correct 277 ms 69264 KB Output is correct
51 Correct 262 ms 74680 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2433 ms 207720 KB Output is correct
2 Correct 1590 ms 228696 KB Output is correct
3 Correct 776 ms 123580 KB Output is correct
4 Correct 2619 ms 195784 KB Output is correct
5 Correct 1579 ms 228008 KB Output is correct
6 Correct 1414 ms 228480 KB Output is correct
7 Correct 757 ms 123532 KB Output is correct
8 Correct 2507 ms 195756 KB Output is correct
9 Correct 2754 ms 214648 KB Output is correct
10 Correct 1913 ms 227236 KB Output is correct
11 Correct 1416 ms 222632 KB Output is correct
12 Correct 1545 ms 226380 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5046 ms 301940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 5 ms 35152 KB Output is correct
4 Correct 6 ms 35152 KB Output is correct
5 Correct 7 ms 35408 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 37456 KB Output is correct
9 Correct 6 ms 35540 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 7 ms 37524 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 8 ms 37456 KB Output is correct
18 Correct 7 ms 37456 KB Output is correct
19 Correct 7 ms 37360 KB Output is correct
20 Correct 7 ms 37456 KB Output is correct
21 Correct 6 ms 35268 KB Output is correct
22 Correct 7 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37456 KB Output is correct
25 Correct 7 ms 37572 KB Output is correct
26 Correct 8 ms 37456 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 8 ms 37456 KB Output is correct
29 Correct 7 ms 37336 KB Output is correct
30 Correct 7 ms 37456 KB Output is correct
31 Correct 996 ms 119520 KB Output is correct
32 Correct 98 ms 41428 KB Output is correct
33 Correct 821 ms 115384 KB Output is correct
34 Correct 792 ms 113144 KB Output is correct
35 Correct 941 ms 120760 KB Output is correct
36 Correct 993 ms 121260 KB Output is correct
37 Correct 548 ms 112284 KB Output is correct
38 Correct 528 ms 112824 KB Output is correct
39 Correct 439 ms 111016 KB Output is correct
40 Correct 464 ms 111676 KB Output is correct
41 Correct 383 ms 75432 KB Output is correct
42 Correct 401 ms 77496 KB Output is correct
43 Correct 76 ms 42680 KB Output is correct
44 Correct 390 ms 77728 KB Output is correct
45 Correct 387 ms 77756 KB Output is correct
46 Correct 349 ms 77496 KB Output is correct
47 Correct 217 ms 67512 KB Output is correct
48 Correct 274 ms 68796 KB Output is correct
49 Correct 262 ms 72364 KB Output is correct
50 Correct 277 ms 69264 KB Output is correct
51 Correct 262 ms 74680 KB Output is correct
52 Correct 166 ms 53584 KB Output is correct
53 Correct 187 ms 44728 KB Output is correct
54 Correct 506 ms 76216 KB Output is correct
55 Correct 353 ms 71080 KB Output is correct
56 Correct 313 ms 67000 KB Output is correct
57 Correct 409 ms 71320 KB Output is correct
58 Correct 355 ms 69288 KB Output is correct
59 Correct 318 ms 65464 KB Output is correct
60 Correct 394 ms 70336 KB Output is correct
61 Correct 150 ms 53944 KB Output is correct
62 Correct 176 ms 53684 KB Output is correct
63 Correct 334 ms 63936 KB Output is correct
64 Correct 392 ms 72272 KB Output is correct
65 Correct 409 ms 71612 KB Output is correct
66 Correct 396 ms 75672 KB Output is correct
67 Correct 211 ms 41912 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 5 ms 35152 KB Output is correct
3 Correct 5 ms 35152 KB Output is correct
4 Correct 6 ms 35152 KB Output is correct
5 Correct 7 ms 35408 KB Output is correct
6 Correct 8 ms 37456 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 37456 KB Output is correct
9 Correct 6 ms 35540 KB Output is correct
10 Correct 9 ms 37712 KB Output is correct
11 Correct 7 ms 37456 KB Output is correct
12 Correct 8 ms 37456 KB Output is correct
13 Correct 7 ms 37456 KB Output is correct
14 Correct 7 ms 37524 KB Output is correct
15 Correct 8 ms 37456 KB Output is correct
16 Correct 8 ms 37456 KB Output is correct
17 Correct 8 ms 37456 KB Output is correct
18 Correct 7 ms 37456 KB Output is correct
19 Correct 7 ms 37360 KB Output is correct
20 Correct 7 ms 37456 KB Output is correct
21 Correct 6 ms 35268 KB Output is correct
22 Correct 7 ms 35408 KB Output is correct
23 Correct 7 ms 37456 KB Output is correct
24 Correct 7 ms 37456 KB Output is correct
25 Correct 7 ms 37572 KB Output is correct
26 Correct 8 ms 37456 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 8 ms 37456 KB Output is correct
29 Correct 7 ms 37336 KB Output is correct
30 Correct 7 ms 37456 KB Output is correct
31 Correct 996 ms 119520 KB Output is correct
32 Correct 98 ms 41428 KB Output is correct
33 Correct 821 ms 115384 KB Output is correct
34 Correct 792 ms 113144 KB Output is correct
35 Correct 941 ms 120760 KB Output is correct
36 Correct 993 ms 121260 KB Output is correct
37 Correct 548 ms 112284 KB Output is correct
38 Correct 528 ms 112824 KB Output is correct
39 Correct 439 ms 111016 KB Output is correct
40 Correct 464 ms 111676 KB Output is correct
41 Correct 383 ms 75432 KB Output is correct
42 Correct 401 ms 77496 KB Output is correct
43 Correct 76 ms 42680 KB Output is correct
44 Correct 390 ms 77728 KB Output is correct
45 Correct 387 ms 77756 KB Output is correct
46 Correct 349 ms 77496 KB Output is correct
47 Correct 217 ms 67512 KB Output is correct
48 Correct 274 ms 68796 KB Output is correct
49 Correct 262 ms 72364 KB Output is correct
50 Correct 277 ms 69264 KB Output is correct
51 Correct 262 ms 74680 KB Output is correct
52 Correct 2433 ms 207720 KB Output is correct
53 Correct 1590 ms 228696 KB Output is correct
54 Correct 776 ms 123580 KB Output is correct
55 Correct 2619 ms 195784 KB Output is correct
56 Correct 1579 ms 228008 KB Output is correct
57 Correct 1414 ms 228480 KB Output is correct
58 Correct 757 ms 123532 KB Output is correct
59 Correct 2507 ms 195756 KB Output is correct
60 Correct 2754 ms 214648 KB Output is correct
61 Correct 1913 ms 227236 KB Output is correct
62 Correct 1416 ms 222632 KB Output is correct
63 Correct 1545 ms 226380 KB Output is correct
64 Execution timed out 5046 ms 301940 KB Time limit exceeded
65 Halted 0 ms 0 KB -