Submission #390081

#	Time	Username	Problem	Language	Result	Execution time	Memory
390081		phathnv	새 집 (APIO18_new_home)	C++11	47 / 100	5077 ms	102588 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 7;
const int INF = 1e9;

struct Event{
    int t, type, x, ind;
    Event(int _t, int _type, int _x, int _ind){
        t = _t;
        type = _type;
        x = _x;
        ind = _ind;
    }
    bool operator < (const Event &oth){
        if (t != oth.t)
            return t < oth.t;
        return type < oth.type;
    }
};

struct SegmentTree{
    int n;
    vector<int> d;
    void init(int _n){
        n = _n;
        d.assign(n * 4 + 1, 0);
    }
    void update(int id, int l, int r, int pos, int val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            d[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        d[id] = max(d[id << 1], d[id << 1 | 1]);
    }
    int getMax(int id, int l, int r, int u, int v){
        if (v < l || r < u)
            return 0;
        if (u <= l && r <= v)
            return d[id];
        int mid = (l + r) >> 1;
        return max(getMax(id << 1, l, mid, u, v), getMax(id << 1 | 1, mid + 1, r, u, v));
    }

    void update(int pos, int val){
        update(1, 1, n, pos, val);
    }
    int getMax(int l, int r){
        return getMax(1, 1, n, l, r);
    }
} ST;

int n, k, q, answer[N];
vector<int> xCoor;
vector<Event> events;
multiset<int> color[N], val[N];

void UpdatePair(int l, int r, int type){
    l = lower_bound(xCoor.begin(), xCoor.end(), l) - xCoor.begin() + 1;
    r = lower_bound(xCoor.begin(), xCoor.end(), r) - xCoor.begin() + 1;
    if (type == -1)
        val[l].erase(val[l].find(r));
    else
        val[l].insert(r);
    ST.update(l, (val[l].empty()? 0 : *(--val[l].end())));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        xCoor.push_back(x);
        events.push_back(Event(a, 1, x, t));
        events.push_back(Event(b + 1, -1, x, t));
    }
    for(int i = 1; i <= q; i++){
        int l, y;
        cin >> l >> y;
        events.push_back(Event(y, 2, l, i));
    }

    xCoor.push_back(-INF);
    xCoor.push_back(INF);
    sort(xCoor.begin(), xCoor.end());
    xCoor.resize(unique(xCoor.begin(), xCoor.end()) - xCoor.begin());
    sort(events.begin(), events.end());

    ST.init(xCoor.size());
    for(int i = 1; i <= k; i++){
        color[i].insert(-INF);
        color[i].insert(INF);
        UpdatePair(-INF, INF, 1);
    }
    for(Event e : events)
        if (e.type == -1){
            color[e.ind].erase(color[e.ind].find(e.x));
            auto it = color[e.ind].upper_bound(e.x);
            int r = *it;
            int l = *(--it);
            UpdatePair(l, e.x, -1);
            UpdatePair(e.x, r, -1);
            UpdatePair(l, r, 1);
        } else if (e.type == 1){
            auto it = color[e.ind].upper_bound(e.x);
            int r = *it;
            int l = *(--it);
            UpdatePair(l, r, -1);
            UpdatePair(l, e.x, 1);
            UpdatePair(e.x, r, 1);
            color[e.ind].insert(e.x);
        } else {
            int lo = 0, hi = 1e8;
            answer[e.ind] = -1;
            while (lo <= hi){
                int mid = (lo + hi) >> 1;
                int l = lower_bound(xCoor.begin(), xCoor.end(), e.x - mid) - xCoor.begin() + 1;
                int r = upper_bound(xCoor.begin(), xCoor.end(), e.x + mid) - xCoor.begin();
                if (ST.getMax(1, l - 1) <= r){
                    answer[e.ind] = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
        }
    for(int i = 1; i <= q; i++)
        cout << answer[i] << '\n';

    return 0;
}

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