Submission #1161439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161439		crafticat	New Home (APIO18_new_home)	C++20	0 / 100	5095 ms	298128 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>;

constexpr ll INF = 1e15 + 7;

template<bool operMax>
struct Seg
{
    Seg<operMax>* left=  nullptr, *right = nullptr;
    ll l, r, mid, v = operMax ? -INF : INF;
    bool sparse = false;
    map<ll, ll> valuesMap;
    multiset<ll> values;

    Seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2)
    {

    }

    void push()
    {
        if (sparse) return;
        sparse = true;
        if (r - l > 1)
        {
            left = new Seg(l, mid);
            right = new Seg(mid, r);
        }
    }

    ll q(ll a, ll b)
    {
        push();
        if (b <= l or a >= r) return operMax ? -INF : INF;
        if (a <= l and b>= r) return v;
        return operMax ? max(left->q(a, b), right->q(a, b)) : min(left->q(a, b), right->q(a, b));
    }

    void update(ll x, ll u, ll type)
    {
        push();
        if (r - l <= 1)
        {
            // Same position?
            if (valuesMap.count(type)) values.erase(values.find(valuesMap[type]));
            valuesMap[type] = u;
            values.insert(u);
            v = operMax ? *values.rbegin() : *values.begin();
            return;
        }

        if (x < mid)
            left->update(x, u, type);
        else
            right->update(x, u, type);
        v = operMax ? max(left->v, right->v) : min(left->v, right->v);
    }
};

template<bool operMax>
struct Seg2d
{
    Seg2d<operMax>* left = nullptr, *right = nullptr;
    ll l, r, mid;
    Seg<operMax>* v= nullptr;
    bool sparse = false;

    Seg2d(ll l, ll r) : l(l), r(r), mid((l + r) / 2)
    {

        v = new Seg<operMax>(0,INF);
    }

    void push()
    {
        if (sparse) return;
        sparse = true;
        if (r - l > 1)
        {
            left = new Seg2d(l, mid);
            right = new Seg2d(mid, r);
        }
    }

    ll q(ll a, ll b, ll x, ll y)
    {
        push();
        if (b <= l or a >= r) return operMax ? -INF : INF;
        if (a <= l and b >= r)
        {
            return v->q(x, y);
        }

        return operMax ? max({left->q(a,b,x,y), right->q(a,b,x,y)}) : min(left->q(a,b,x,y), right->q(a,b,x,y));
    }

    void update(ll x, ll y, ll z, ll t)
    {
        push();
        if (r - l <= 1)
        {
            v->update(y, z, t);
            return;
        }
        if (x < mid)
            left->update(x, y, z, t);
        else
            right->update(x, y, z, t);
        v->update(y, operMax ? max(left->v->q(y, y + 1),right->v->q(y, y + 1)) : min(left->v->q(y, y + 1),right->v->q(y, y + 1)), 0);
    }
};

Seg2d<true> *maxSeg = nullptr;
Seg2d<false> *minSeg = nullptr;
V<multiset<ll>> polls;
ll amount = 0;

void addSeg(ll l, ll r, ll x, ll t)
{
    if (x == -1)
    {
        maxSeg->update(l, r, -INF, t);
        minSeg->update(l, r, INF, t);
    } else
    {
        maxSeg->update(l, r, x, t);
        minSeg->update(l, r, x, t);
    }
}
ll query(ll x)
{
    ll y = maxSeg->q(0, x + 1, x + 1, INF);
    ll z = minSeg->q(0, x + 1, x + 1, INF);

    ll ans = max(abs(x - y), abs(z - x));
    if (amount < 0) return -1;
    return ans > (ll) 1e9 ? -1 : ans;
}

void add(ll x, ll t)
{
    if (polls[t].size() > 1) amount--;

    auto it = polls[t].lower_bound(x);
    ll after = it == polls[t].end() ? INF : *it;
    ll before = it == polls[t].begin() ? -INF : *--it;
    ll mid = (before + after) / 2;
    ll mid1 = (before + x) / 2, mid2 = (after + x) / 2;
    addSeg(before, mid, -1, t);
    addSeg(mid, after, -1, t);
    addSeg(before, mid1, before, t);
    addSeg(mid1, x, x, t);
    addSeg(mid2, after, after, t);
    addSeg(x, mid2, x, t);

    polls[t].insert(x);
    if (polls[t].size() > 1) amount++;

}
void del(ll x,ll t)
{
    if (polls[t].size() > 1) amount--;

    auto it2 = polls[t].find(x);
    if (it2 != polls[t].end()) polls[t].erase(it2);
    auto it = polls[t].lower_bound(x);

    ll after = it == polls[t].end() ? INF : *it;
    ll before = it == polls[t].begin() ? -INF : *--it;
    ll mid = (before + after) / 2;
    ll mid1 = (before + x) / 2, mid2 = (after + x) / 2;

    addSeg(before, mid, before, t);
    addSeg(mid, after, after, t);

    addSeg(before, mid1, -1, t);
    addSeg(mid1, x, -1, t);
    addSeg(mid2, after, -1, t);
    addSeg(x, mid2, -1, t);
    if (polls[t].size() > 1) amount++;
}

int main()
{
    ll n, k, q; cin >> n >> k >> q;
    V<tuple<ll,ll,ll,ll>> updates; // Add time, Type, Pos, TypeX
    // Ins, Query, Del
    vi results(q);

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

    amount = -k;
    ll t = 0;
    while (q--)
    {
        ll l, y; cin >> l >> y;
        updates.emplace_back(y, 2, l, t++);
    }

    sort(updates.begin(), updates.end());

    polls.resize(k);
    maxSeg = new Seg2d<true>(0, INF);
    minSeg = new Seg2d<false>(0, INF);

    F0R(i, k)
    {
        add(-INF, i);
    }


    for (auto [time, type, pos, typeX] : updates)
    {
        typeX--;
        if (type == 1)
        {
            add(pos, typeX);
        }
        if (type == 2)
        {
            typeX++;
            results[typeX] = query(pos);
        }
        if (type == 3)
        {
            del(pos, typeX);
        }
    }

    for (auto x : results)
        cout << x << '\n';
    return 0;
}

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