Submission #389778

#	Time	Username	Problem	Language	Result	Execution time	Memory
389778		phathnv	New Home (APIO18_new_home)	C++11	5 / 100	2779 ms	1048580 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;
    }
};

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

void updateSeg(int l, int r, int x, int type){
    for(int i = 0; i < (int) xCoor.size(); i++)
        if (l <= xCoor[i] && xCoor[i] <= r){
            if (type == 1)
                val[i].insert(abs(x - xCoor[i]));
            else
                val[i].erase(val[i].find(abs(x - xCoor[i])));
        }
}

void updatePair(int l, int r, int type){
    int mid = (l + r) >> 1;
    updateSeg(l, mid, l, type);
    updateSeg(mid + 1, r, r, type);
}

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());

    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 p = lower_bound(xCoor.begin(), xCoor.end(), e.x) - xCoor.begin();
            answer[e.ind] = *(--val[p].end());
        }
    }
    for(int i = 1; i <= q; i++)
        cout << (answer[i] > 1e8? -1 : answer[i]) << '\n';
    return 0;
}

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