Submission #390110

#	Time	Username	Problem	Language	Result	Execution time	Memory
390110		phathnv	New Home (APIO18_new_home)	C++11	100 / 100	4348 ms	89996 KiB

new_home

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

typedef long long ll;

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

struct Coor{
    int x, t;
    Coor(int _x = 0, int _t = 0){
        x = _x;
        t = _t;
    }
    bool operator < (const Coor &oth) const {
        if (x != oth.x)
            return x < oth.x;
        return t < oth.t;
    }
    bool operator == (const Coor &oth) const {
        return (x == oth.x && t == oth.t);
    }
};

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) const {
        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 * 2, 0);
    }
    void update(int pos, int val){
        assert(pos < n);
        pos += n;
        d[pos] = val;
        for(; pos; pos >>= 1)
            d[pos >> 1] = max(d[pos], d[pos ^ 1]);
    }
    int getMax(int l, int r){
        int res = 0;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1){
            if (l & 1)
                res = max(res, d[l++]);
            if (r & 1)
                res = max(res, d[--r]);
        }
        return res;
    }
} ST;

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

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(Coor{x, t});
        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));
    }
    for(int i = 1; i <= k; i++)
        xCoor.push_back(Coor(-INF, i));
    sort(xCoor.begin(), xCoor.end());
    xCoor.resize(unique(xCoor.begin(), xCoor.end()) - xCoor.begin());
    sort(events.begin(), events.end());
    for(Event &e : events)
        if (e.type != 2)
            e.x = lower_bound(xCoor.begin(), xCoor.end(), Coor(e.x, e.ind)) - xCoor.begin();

    ST.init(xCoor.size());
    for(int i = 1; i <= k; i++){
        color[i].insert(i - 1);
        color[i].insert(INF);
        ST.update(i - 1, INF);
    }
    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);
            ST.update(e.x, 0);
            ST.update(l, r);
        } else if (e.type == 1){
            auto it = color[e.ind].upper_bound(e.x);
            int r = *it;
            int l = *(--it);
            ST.update(l, e.x);
            ST.update(e.x, r);
            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(), Coor(e.x - mid, -INF)) - xCoor.begin();
                int r = upper_bound(xCoor.begin(), xCoor.end(), Coor(e.x + mid, INF)) - xCoor.begin() - 1;
                if (ST.getMax(0, l) <= 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: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20