Submission #1160921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160921		crafticat	새 집 (APIO18_new_home)	C++20	0 / 100	4292 ms	1114112 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

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

template<typename T>
using V = vector<T>;
using vi = vector<int>;

constexpr int INF = 1e9 + 7;

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

    Seg(int l, int 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);
        }
    }

    int q(int a, int 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(int x, int u)
    {
        push();
        if (r - l <= 1)
        {
            v = u;
            return;
        }

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

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

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

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

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

    int q(int a, int b, int x, int 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(int x, int y, int z)
    {
        push();
        if (r - l <= 1)
        {
            v->update(y, z);
            return;
        }
        if (x < mid)
            left->update(x, y, z);
        else
            right->update(x, y, z);
        v->update(y, z);
    }
};

Seg2d<true> *maxSeg = nullptr;
Seg2d<true> *minSeg = nullptr;
V<set<int>> points;

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

    return max(abs(x - y), abs(z - x));
}

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

    points[t].insert(x);
}
void del(int x,int t)
{
    points[t].erase(x);
    auto it = points[t].lower_bound(x);

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

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

    addSeg(before, mid1, -1);
    addSeg(mid1, x, -1);
    addSeg(mid2, after, -1);
    addSeg(x, mid2, -1);
}

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

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

    while (q--)
    {
        int l, y; cin >> l >> y;
        updates.emplace_back(y, 2, l, -1);
    }

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

    points.resize(k);
    maxSeg = new Seg2d<true>(0, INF);
    minSeg = new Seg2d<true>(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)
        {
            int ans = query(pos);
            if (ans >= 1e8) ans = -1;
            cout << ans << "\n";
        }
        if (type == 3)
        {
            del(pos, typeX);
        }
    }
}

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