Submission #389814

#	Time	Username	Problem	Language	Result	Execution time	Memory
389814		phathnv	New Home (APIO18_new_home)	C++11	47 / 100	5098 ms	372332 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, x[N];
    multiset<int> setLeft[N * 4], setRight[N * 4];
    void init(const vector<int> &xCoor){
        n = xCoor.size();
        for(int i = 1; i <= n; i++)
            x[i] = xCoor[i - 1];
    }
    void updateSeg(int id, int l, int r, int u, int v, int val, int type, multiset<int> d[]){
        if (v < x[l] || x[r] < u)
            return;
        if (u <= x[l] && x[r] <= v){
            if (type == -1)
                d[id].erase(d[id].find(val));
            else
                d[id].insert(val);
            return;
        }
        int mid = (l + r) >> 1;
        updateSeg(id << 1, l, mid, u, v, val, type, d);
        updateSeg(id << 1 | 1, mid + 1, r, u, v, val, type, d);
    }
    int getMax(int id, int l, int r, int pos){
        if (pos < x[l] || x[r] < pos)
            return 0;
        int res = 0;
        if (!setLeft[id].empty())
            res = max(res, pos + *(--setLeft[id].end()));
        if (!setRight[id].empty())
            res = max(res, *(--setRight[id].end()) - pos);

        if (l == r)
            return res;
        int mid = (l + r) >> 1;
        res = max(res, getMax(id << 1, l, mid, pos));
        res = max(res, getMax(id << 1 | 1, mid + 1, r, pos));
        return res;
    }
    void updatePair(int l, int r, int type){
        int mid = (l + r) >> 1;
        updateSeg(1, 1, n, l, mid, -l, type, setLeft);
        updateSeg(1, 1, n, mid + 1, r, r, type, setRight);
    }
    int getMax(int pos){
        return getMax(1, 1, n, pos);
    }
} ST;

int n, k, q, answer[N];
vector<Event> events;
vector<int> xCoor;
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;
        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 x, y;
        cin >> x >> y;
        events.push_back(Event(y, 2, x, i));
        xCoor.push_back(x);
    }

    sort(events.begin(), events.end());
    sort(xCoor.begin(), xCoor.end());
    xCoor.resize(unique(xCoor.begin(), xCoor.end()) - xCoor.begin());
    ST.init(xCoor);

    for(int i = 1; i <= k; i++){
        color[i].insert(-INF);
        color[i].insert(INF);
        ST.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);
            ST.updatePair(l, e.x, -1);
            ST.updatePair(e.x, r, -1);
            ST.updatePair(l, r, 1);
        } else if (e.type == 1){
            auto it = color[e.ind].upper_bound(e.x);
            int r = *it;
            int l = *(--it);
            ST.updatePair(l, r, -1);
            ST.updatePair(l, e.x, 1);
            ST.updatePair(e.x, r, 1);
            color[e.ind].insert(e.x);
        } else {
            answer[e.ind] = ST.getMax(e.x);
        }
    }
    for(int i = 1; i <= q; i++)
        cout << (answer[i] > 1e8? -1 : 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