Submission #260930

#	Time	Username	Problem	Language	Result	Execution time	Memory
260930		SorahISA	New Home (APIO18_new_home)	C++17	12 / 100	5060 ms	50544 KiB

new_home

#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)

const int INF = 0x7f7f7f7f;
const int maxn = 3E5 + 5;

struct Store {
    int x, t, a, b, id;
};

struct Query {
    int l, y, id;
};

int32_t main() {
    fastIO();
    
    int n, k, q;
    cin >> n >> k >> q;
    
    vector<Store> store(n);
    for (int i = 0; i < n; ++i) {
        cin >> store[i].x >> store[i].t >> store[i].a >> store[i].b;
        store[i].id = i;
    }
    sort(ALL(store), [](auto s1, auto s2) {
        if (s1.a == s2.a) return s1.b < s2.b;
        return s1.a < s2.a;
    });
    
    vector<Query> ask(q);
    for (int i = 0; i < q; ++i) {
        cin >> ask[i].l >> ask[i].y;
        ask[i].id = i;
    }
    sort(ALL(ask), [](auto q1, auto q2) {
        if (q1.y == q2.y) return q1.l < q2.l;
        return q1.y < q2.y;
    });
    
    vector<int> ans(q);
    multiset<pii> pl[k + 1];
    for (int j = 1; j <= k; ++j) pl[j].insert({-INF, INF}), pl[j].insert({INF, INF});
    for (int i = 0, tok = 0; i < q; ++i) {
        while (tok < n and store[tok].a <= ask[i].y) pl[store[tok].t].insert({store[tok].x, store[tok].b}), ++tok;
        int maxDis = 0;
        for (int j = 1; j <= k; ++j) {
            auto it1 = pl[j].begin(), it2 = it1;
            while ((it1 =      pl[j].lower_bound({ask[i].l, 0LL}) , 1) and (*it1).Y < ask[i].y) pl[j].erase(it1);
            while ((it2 = prev(pl[j].lower_bound({ask[i].l, 0LL})), 1) and (*it2).Y < ask[i].y) pl[j].erase(it2);
            // for (auto qry : pl[j]) cout << "[" << qry.X << "," << qry.Y << "]"; cout << (*it1).X << " " << (*it2).X << "\n";
            maxDis = max(maxDis, min(abs(ask[i].l - (*it1).X), abs(ask[i].l - (*it2).X)));
        }
        ans[ask[i].id] = maxDis > 1E8 ? -1 : maxDis;
    }
    
    for (auto x : ans) cout << x << "\n";
    
    return 0;
}

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