Submission #742819

#	Time	Username	Problem	Language	Result	Execution time	Memory
742819		PixelCat	New Home (APIO18_new_home)	C++14	12 / 100	5065 ms	63776 KiB

new_home

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 300030;
const int INF = 1e12;

struct Line {
    int m, c;  // mx + c
    Line(int _m = 0, int _c = 0): m(_m), c(_c) {}
    int operator()(int x) {
        return m * x + c;
    }
};
Line operator+(const Line& a, const Line& b) {
    return Line(a.m + b.m, a.c + b.c);
}
Line operator-(const Line& a, const Line& b) {
    return Line(a.m - b.m, a.c - b.c);
}

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    // TODO
} seg;

struct Event {
    int pos, time, type, add;
    // add: 49 = query, 1 = insert, -1 = erase
}; deque<Event> dq;

multiset<int> st[MAXN];
int ans[MAXN];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^= nya
    int n, k, q; cin >> n >> k >> q;
    For(i, 1, n) {
        int x, t, a, b; cin >> x >> t >> a >> b;
        dq.eb((Event){ x, a, t, 1 });
        dq.eb((Event){ x, b + 1, t, -1 });
    }
    For(i, 1, q) {
        int p, t; cin >> p >> t;
        dq.eb((Event){p, t, i, 49});
    }
    sort(all(dq), [&](const Event &a, const Event &b) {
        if(a.time != b.time) return a.time < b.time;
        return a.add < b.add;
    });

    while(!dq.empty()) {
        auto e = dq.front(); dq.pop_front();

        if(e.add == 49) {
            // query
            int mx = -1;
            For(i, 1, k) {
                int tmp = INF;
                auto it = st[i].lower_bound(e.pos);
                if(it != st[i].end()) {
                    tmp = min(tmp, abs(e.pos - (*it)));
                }
                if(it != st[i].begin()) {
                    it = prev(it);
                    tmp = min(tmp, abs(e.pos - (*it)));
                }
                mx = max(mx, tmp);
            }
            if(mx >= INF) mx = -1;
            ans[e.type] = mx;
        } else if(e.add == 1) {
            // insert
            st[e.type].insert(e.pos);
        } else if(e.add == -1) {
            // erase
            st[e.type].erase(st[e.type].find(e.pos));
        }
    }

    For(i, 1, q) cout << ans[i] << "\n";
    return 0;
}

/*

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1

*/

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