제출 #1165666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165666		anmattroi	새 집 (APIO18_new_home)	C++20	10 / 100	5037 ms	600156 KiB

new_home

#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 300005
using namespace std;
using ii = pair<int, int>;
//dynamic IT is way, way more convenient

const int MAX = 100'000'000;

int itL[16*maxn], itR[16*maxn];
int coor[4*maxn], ddi = 0;


int nt = 0;

struct node {
    int val;
    vector<ii> traceL, traceR;

    node() {}
    node(int _val) : val(_val) {}
};

void update_L(int u, int v, node &cur, int r = 1, int lo = 1, int hi = ddi) {
    if (u <= lo && hi <= v) {
        int cr = cur.val-(coor[lo]-coor[u]);
        if (itL[r] < cr) {
            cur.traceL.emplace_back(r, itL[r]);
            itL[r] = cr;
        }
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) update_L(u, v, cur, r<<1, lo, mid);
    if (v >  mid) update_L(u, v, cur, r<<1|1, mid+1, hi);
}

void update_R(int u, int v, node &cur, int r = 1, int lo = 1, int hi = ddi) {
    if (u <= lo && hi <= v) {
        int cr = cur.val-(coor[v]-coor[hi]);
        if (itR[r] < cr) {
            cur.traceR.emplace_back(r, itR[r]);
            itR[r] = cr;
        }
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) update_R(u, v, cur, r<<1, lo, mid);
    if (v  > mid) update_R(u, v, cur, r<<1|1, mid+1, hi);

}

int get(int u, int r = 1, int lo = 1, int hi = ddi) {
    if (lo == hi) return max(itL[r], itR[r]);
    int mid = (lo + hi) >> 1;
    if (u <= mid) return max({itL[r]-(coor[u]-coor[lo]), itR[r]-(coor[hi]-coor[u]), get(u, r<<1, lo, mid)});
    return max({itL[r]-(coor[u]-coor[lo]), itR[r]-(coor[hi]-coor[u]), get(u, r<<1|1, mid+1,hi)});

}

int n, k, q;

struct store {
    int x, type, a, b;
    store() {}
    store(int _x, int _type, int _a, int _b) : x(_x), type(_type), a(_a), b(_b) {}
} stores[maxn];

struct query {
    int l, y;
    query() {}
    query(int _l, int _y) : l(_l), y(_y) {}
} queries[maxn];

int years[3*maxn], id = 0, ans[maxn];

map<int, int> cur_pos[maxn];

struct event {
    int type, store_type, pos;
    event() {}
    event(int _type, int _store_type, int _pos) : type(_type), store_type(_store_type), pos(_pos) {}
};

vector<event> events[12*maxn];
vector<node> nodes[12*maxn];

int number_of_available = 0;

void updateL(int u, int v, node &cur) {
    int p = lower_bound(coor + 1, coor + ddi + 1, u) - coor,
        q = lower_bound(coor + 1, coor + ddi + 1, v) - coor;
    update_L(p, q, cur);
}

void updateR(int u, int v, node &cur) {
    int p = lower_bound(coor + 1, coor + ddi + 1, u) - coor,
        q = lower_bound(coor + 1, coor + ddi + 1, v) - coor;
    update_R(p, q, cur);
}

int git(int u) {
    int p = lower_bound(coor + 1, coor + ddi + 1, u) - coor;
    return get(p);
}
void del(int x, int type, vector<node> &cur) {
    map<int, int> &cr = cur_pos[type];
    --cr[x];
    if (cr[x] > 0) return;
    cr.erase(x);
    if (cr.empty()) {
        --number_of_available;
        return;
    }
    auto it = cr.lower_bound(x);
    cur.emplace_back(-1);
    if (it == cr.end()) {
        auto [p, c] = *prev(it);
        cur.back().val = MAX-p;
        updateR(p, MAX, cur.back());
    }
    if (it == cr.begin()) {
        auto [p, c] = *it;
        cur.back().val = p-1;
        updateL(1, p, cur.back());
    }
    if (it != cr.begin() && it != cr.end()) {
        auto [p1, c1] = *prev(it);
        auto [p2, c2] = *it;
        int mid = (p1+p2)>>1;
        if (mid != p1) {
            cur.back().val = mid-p1;
            updateR(p1, mid, cur.back());
        }
        if(mid+1!= p2) {
            cur.back().val = p2-mid-1;
            updateL(mid+1,p2, cur.back());
        }
    }
}

void add_event(int u, int v, const event &t, int r = 1, int lo = 1, int hi = id) {
    if (u <= lo && hi <= v) {
        events[r].emplace_back(t);
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) add_event(u, v, t, r<<1, lo, mid);
    if (v  > mid) add_event(u, v, t, r<<1|1,mid+1,hi);
}

void dfs(int r = 1, int lo = 1, int hi = id) {
    for (event &xd : events[r]) {
        if (xd.type == 1) {
            del(xd.pos, xd.store_type, nodes[r]);
            continue;
        }
        ans[xd.store_type] = (number_of_available != k ? -1 : git(xd.pos));
    }
    if (lo != hi) {
        int mid = (lo + hi) >> 1;
        dfs(r<<1, lo, mid);
        dfs(r<<1|1, mid+1, hi);
    }
    for (event &xd : events[r]) {
        if (xd.type == 2) continue;
        if (cur_pos[xd.store_type].empty()) ++number_of_available;
        cur_pos[xd.store_type][xd.pos]++;
    }
    for (int o = int(nodes[r].size())-1; o >= 0; o--) {
        node &cur = nodes[r][o];
        for (auto [pos, val] : cur.traceL) itL[pos] = val;
        for (auto [pos, val] : cur.traceR) itR[pos] = val;
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k >> q;
    coor[++ddi] = 1; coor[++ddi] = MAX;
    for (int i = 1; i <= n; i++) {
        cin >> stores[i].x >> stores[i].type >> stores[i].a >> stores[i].b;
        years[++id] = stores[i].a;
        years[++id] = stores[i].b;
        cur_pos[stores[i].type][stores[i].x]++;
        coor[++ddi] = stores[i].x;
    }
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].l >> queries[i].y;
        years[++id] = queries[i].y;
        coor[++ddi] = queries[i].l;
    }
    sort(years + 1, years + id + 1);
    id = unique(years + 1, years + id + 1) - years - 1;

    for (int i = 1; i <= n; i++) {
        auto [x, type, a, b] = stores[i];
        int p = lower_bound(years + 1, years + id + 1, a) - years,
            q = lower_bound(years + 1, years + id + 1, b) - years;
        if (1 < p) add_event(1, p-1, event(1, type, x));
        if (q <id) add_event(q+1,id, event(1, type, x));
    }
    for (int i = 1; i <= q; i++) {
        auto [l, y] = queries[i];
        int p = lower_bound(years + 1, years + id + 1, y) - years;
        add_event(p, p, event(2, i, l));
    }
    for (int type = 1; type <= k; type++) {
        if (cur_pos[type].empty()) {
            for (int i = 1; i <= q; i++) cout << "-1\n";
            exit(0);
        }
        for (auto it = next(cur_pos[type].begin()); it != cur_pos[type].end(); it++) {
            int A = prev(it)->fi, B = it->fi;
            int mid = (A + B) >> 1;
            coor[++ddi] = mid;
            coor[++ddi] = mid+1;
        }
    }
    sort(coor+1, coor+ddi+1);
    ddi = unique(coor + 1, coor + ddi + 1) - coor - 1;

    for (int type = 1; type <= k; type++) {
        for (auto it = cur_pos[type].begin(); it != cur_pos[type].end(); it++) {
            if (it == cur_pos[type].begin()) {
                node tmp = node(it->fi-1);
                updateL(1, it->fi, tmp);
            } else {
                int A = prev(it)->fi, B = it->fi;
                int mid = (A + B) >> 1;
                if (A != mid) {
                    node tmp = node(mid-A);
                    updateR(A, mid, tmp);
                }
                if (mid+1 != B) {
                    node tmp = node(B-mid-1);
                    updateL(mid+1, B, tmp);
                }
            }
            if (next(it) == cur_pos[type].end()) {
                node tmp = node(MAX-it->fi);
                updateR(it->fi, MAX, tmp);
            }
        }
    }
    number_of_available = k;
    dfs();

    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";



}
/*
20 4 20
61418457 4 33932551 98975124
50805588 3 56616927 66076460
44262243 1 58029464 59272268
34981593 4 10760710 89302332
58741675 3 60670049 77700264
33623668 3 63722438 67824726
62526450 2 43078579 75611393
4274055 2 14095759 73162733
87374777 4 83277088 91743411
94571186 3 89842706 99458411
12478656 1 55215479 64580090
46403286 1 64108098 88220140
25238282 3 27675595 60451597
37952789 3 75386446 86876313
54809046 2 464235 94068753
54550479 4 43413159 82041311
60506534 1 36798954 58908977
6850469 3 62412544 96889167
11487035 1 27483928 65012744
25556601 3 56979016 64631117
43829142 75778104
4327430 69657358
67266924 62503955
91098800 17217564
36980472 9907558
55411206 60398483
10853597 89800178
36326059 47454979
18873570 69037881
6872487 5699329
72919664 13874179
36117991 30130855
20960277 40510938
67013052 11520529
47497475 62411149
63643480 32071905
66382737 55172529
60322388 48398523
89865913 51148827
28250669 81786058
*/
/*
10979904
42075856
54788268
-1
-1
42932550
-1
24180475
27529716
-1
-1
24630956
16686222
-1
35018819
52156445
41144455
35084106
64627631
26558377
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20