oj.uz

답안 #1107860

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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
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 = 2e6 + 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[N], l[N], r[N];
    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;
            }
            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';
    }

    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){
    if(*(--spl[i].end()) == x1){
        lt.zer(0, L, R, i);
        spl[i].erase(spl[i].find(x1));
        if(spl[i].size() > 0)
            lt.add(0, L, R, i, *(--spl[i].end()));
    }else{
        spl[i].erase(spl[i].find(x1));
    }
    if(*(--spr[i].end()) == x2){
        rt.zer(0, L, R, i);
        spr[i].erase(spr[i].find(x2));
        if(spr[i].size() > 0)
            rt.add(0, L, R, i, *(--spr[i].end()));
    }else{
        spr[i].erase(spr[i].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 6 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 6 ms 35408 KB Output is correct
6 Correct 8 ms 35664 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 35408 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 35832 KB Output is correct
11 Correct 7 ms 35408 KB Output is correct
12 Correct 8 ms 35664 KB Output is correct
13 Correct 9 ms 35408 KB Output is correct
14 Correct 8 ms 35408 KB Output is correct
15 Correct 7 ms 35408 KB Output is correct
16 Correct 8 ms 35408 KB Output is correct
17 Correct 8 ms 35408 KB Output is correct
18 Correct 7 ms 35408 KB Output is correct
19 Correct 7 ms 35408 KB Output is correct
20 Correct 7 ms 35408 KB Output is correct
21 Correct 7 ms 35408 KB Output is correct
22 Correct 7 ms 35440 KB Output is correct
23 Correct 6 ms 35408 KB Output is correct
24 Correct 7 ms 35408 KB Output is correct
25 Correct 7 ms 35556 KB Output is correct
26 Correct 7 ms 35408 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 6 ms 35408 KB Output is correct
29 Correct 6 ms 35408 KB Output is correct
30 Correct 6 ms 35408 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 6 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 6 ms 35408 KB Output is correct
6 Correct 8 ms 35664 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 35408 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 35832 KB Output is correct
11 Correct 7 ms 35408 KB Output is correct
12 Correct 8 ms 35664 KB Output is correct
13 Correct 9 ms 35408 KB Output is correct
14 Correct 8 ms 35408 KB Output is correct
15 Correct 7 ms 35408 KB Output is correct
16 Correct 8 ms 35408 KB Output is correct
17 Correct 8 ms 35408 KB Output is correct
18 Correct 7 ms 35408 KB Output is correct
19 Correct 7 ms 35408 KB Output is correct
20 Correct 7 ms 35408 KB Output is correct
21 Correct 7 ms 35408 KB Output is correct
22 Correct 7 ms 35440 KB Output is correct
23 Correct 6 ms 35408 KB Output is correct
24 Correct 7 ms 35408 KB Output is correct
25 Correct 7 ms 35556 KB Output is correct
26 Correct 7 ms 35408 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 6 ms 35408 KB Output is correct
29 Correct 6 ms 35408 KB Output is correct
30 Correct 6 ms 35408 KB Output is correct
31 Runtime error 213 ms 135132 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 514 ms 206240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 423 ms 190808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 6 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 6 ms 35408 KB Output is correct
6 Correct 8 ms 35664 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 35408 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 35832 KB Output is correct
11 Correct 7 ms 35408 KB Output is correct
12 Correct 8 ms 35664 KB Output is correct
13 Correct 9 ms 35408 KB Output is correct
14 Correct 8 ms 35408 KB Output is correct
15 Correct 7 ms 35408 KB Output is correct
16 Correct 8 ms 35408 KB Output is correct
17 Correct 8 ms 35408 KB Output is correct
18 Correct 7 ms 35408 KB Output is correct
19 Correct 7 ms 35408 KB Output is correct
20 Correct 7 ms 35408 KB Output is correct
21 Correct 7 ms 35408 KB Output is correct
22 Correct 7 ms 35440 KB Output is correct
23 Correct 6 ms 35408 KB Output is correct
24 Correct 7 ms 35408 KB Output is correct
25 Correct 7 ms 35556 KB Output is correct
26 Correct 7 ms 35408 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 6 ms 35408 KB Output is correct
29 Correct 6 ms 35408 KB Output is correct
30 Correct 6 ms 35408 KB Output is correct
31 Runtime error 213 ms 135132 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 6 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 6 ms 35408 KB Output is correct
6 Correct 8 ms 35664 KB Output is correct
7 Correct 7 ms 35408 KB Output is correct
8 Correct 7 ms 35408 KB Output is correct
9 Correct 7 ms 35408 KB Output is correct
10 Correct 8 ms 35832 KB Output is correct
11 Correct 7 ms 35408 KB Output is correct
12 Correct 8 ms 35664 KB Output is correct
13 Correct 9 ms 35408 KB Output is correct
14 Correct 8 ms 35408 KB Output is correct
15 Correct 7 ms 35408 KB Output is correct
16 Correct 8 ms 35408 KB Output is correct
17 Correct 8 ms 35408 KB Output is correct
18 Correct 7 ms 35408 KB Output is correct
19 Correct 7 ms 35408 KB Output is correct
20 Correct 7 ms 35408 KB Output is correct
21 Correct 7 ms 35408 KB Output is correct
22 Correct 7 ms 35440 KB Output is correct
23 Correct 6 ms 35408 KB Output is correct
24 Correct 7 ms 35408 KB Output is correct
25 Correct 7 ms 35556 KB Output is correct
26 Correct 7 ms 35408 KB Output is correct
27 Correct 7 ms 35408 KB Output is correct
28 Correct 6 ms 35408 KB Output is correct
29 Correct 6 ms 35408 KB Output is correct
30 Correct 6 ms 35408 KB Output is correct
31 Runtime error 213 ms 135132 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -