Submission #390094

#	Time	Username	Problem	Language	Result	Execution time	Memory
390094		phathnv	New Home (APIO18_new_home)	C++11	33 / 100	4904 ms	102596 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 * 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<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() + 1;

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