Submission #1161016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161016		crafticat	New Home (APIO18_new_home)	C++20	0 / 100	5096 ms	47632 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

#define F0R(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define ROF(i, a, b) for (ll i = (a); i >= (b); i--)
#define REP(i, n) for (ll i = (n); i >= 0; i--)

using ll = long long;
template<typename T>
using V = vector<T>;
using vi = vector<ll>;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll n, k, q; cin >> n >> k >> q;
    V<tuple<ll,ll,ll,ll>> updates; // Add time, Type, Pos, TypeX
    // Ins, Query, Del

    F0R(i, n)
    {
        ll x, t, a, b; cin >> x >> t >> a >> b;
        updates.emplace_back(a, 1, x, t);
        updates.emplace_back(b, 3, x, t);
    }

    V<ll> queries(q);
    int id = 0;
    while (q--)
    {
        ll l, y; cin >> l >> y;
        updates.emplace_back(y, 2, l, id++);
    }

    sort(updates.begin(), updates.end());
    V<multiset<ll>> items(k);

    for (auto [t, type, pos, posX] : updates)
    {
        posX--;

        if (type == 1)
        {
            items[posX].insert(pos);
        }
        if (type == 2)
        {
            ll ans = 0;
            F0R(i, k)
            {
                ll closest = 1e18;
                for (auto x : items[i])
                {
                    closest = min(closest, abs(x - pos));
                }
                ans = max(ans, closest);
            }
            queries[posX] = ans == (ll) 1e8 ? -1 : ans;
        }
        if (type == 3)
        {
            items[posX].erase(items[posX].find(pos));
        }
    }
    F0R(i, queries.size())
    {
        cout << queries[i] << "\n";
    }
}

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