제출 #1319590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319590		fateless	새 집 (APIO18_new_home)	C++20	12 / 100	5091 ms	71036 KiB

new_home

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

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;

#define now chrono::steady_clock::now().time_since_epoch().count()
#define speedup cin.tie(0)->sync_with_stdio(0)
#define bitcount(x) __builtin_popcountll(x)
#define lla(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define Tp template <class T>
#define int long long
#define pb push_back
#define vc vector
#define arr array

Tp using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;

const int inf = 1e18;
inline void solve () {
    int n, k, q;
    cin >> n >> k >> q;
    vc<array<int, 5>> e;
    vc<vc<int>> cmp (k + 1);
    vc<oset<pii>> s (k + 1);
    for (int i = 1; i <= n; i++) {
        int x, t, a, b;cin >> x >> t >> a >> b;
        e.pb({a, 1, x, t, i}); e.pb({b, 3, x, t, i});
        cmp[t].pb(a); cmp[t].pb(b);
    }

    vc<int> ansq (q);
    for (int i = 0; i < q; i++) {
        int t, x; cin >> x >> t;
        e.pb({t, 2, x, i, 0});
    }

    // e = { time, type, id, class, unique number for oset }

    sort(all(e));
    for (auto [time, tp, id, i, j] : e) {
        if (tp == 1) s[i].insert({id, j});
        else if (tp == 3) s[i].erase({id, j});
        else {
            int ans = 0;
            for (int l = 1; l <= k; l++) {
                int res = inf;
                if (s[l].empty()) {
                    ans = -1;
                    break;
                }

                auto it = s[l].upper_bound({id, inf});
                res = min(res, abs(id - it -> first));
                if (it != begin(s[l])) {
                    --it;
                    res = min(res, abs(id - it -> first));
                }

                ans = max(ans, res);
            }
            ansq[i] = ans;
        }
    }
    for (int &x : ansq) cout << x << '\n';
}

signed main() {
    speedup;
    solve();

    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

*/

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