제출 #375983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375983		usachevd0	새 집 (APIO18_new_home)	C++14	80 / 100	5111 ms	257084 KiB

new_home

#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc target("avx2")
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <fstream>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <random>
#include <time.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(...) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &a) { for (auto& x : a) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2> &a) { stream << a.fi << ' ' << a.se; return stream; }

const int INF32 = 0x3f3f3f3f;
const int N = 3e5 + 5;
bool task3, task34;
int rx[2 * N], X;
int n, Q, types;
struct shop_t
{
    int x, tp, t1, t2;
} s[N];
struct query_t
{
    int x, t, idx;
} qr[N];
int ans[N];

struct event_t
{
    int t, tp, idx;

    bool operator < (const event_t& oth) const
    {
        if (t != oth.t)
            return t < oth.t;
        return tp < oth.tp;
    }
} ev[3 * N];
int events;

map<int, int> type_on[N];
int tp_cnt[N];

namespace treap
{
    mt19937 rng(time(0));
    struct Node
    {
        int x, y;
        Node *l, *r;

        Node() {}
        Node(int _x): x(_x), y(rng()), l(0), r(0) {}
    };
    Node* merge(Node* a, Node* b)
    {
        if (!a) return b;
        if (!b) return a;
        if (a->y > b->y)
        {
            a->r = merge(a->r, b);
            return a;
        }
        else
        {
            b->l = merge(a, b->l);
            return b;
        }
    }
    pair<Node*, Node*> split(Node *t, int x)
    {
        if (!t) return {0, 0};
        if (t->x < x)
        {
            auto p = split(t->r, x);
            t->r = p.fi;
            return {t, p.se};
        }
        else
        {
            auto p = split(t->l, x);
            t->l = p.se;
            return {p.fi, t};
        }
    }
    void add(Node *&t, int x)
    {
        auto p = split(t, x);
        t = merge(p.fi, merge(new Node(x), p.se));
    }
    void rem(Node *&t, int x)
    {
        if (!t) return;
        if (t->x == x)
        {
            t = merge(t->l, t->r);
        }
        else if (t->x < x)
        {
            rem(t->r, x);
        }
        else
        {
            rem(t->l, x);
        }
    }
    int gmin(Node *t)
    {
        if (!t) return INF32;
        for (; t->l; t = t->l);
        return t->x;
    }
    int gmax(Node *t)
    {
        if (!t) return INF32;
        for (; t->r; t = t->r);
        return t->x;
    }
}

namespace sgt
{
    const int logN = 20;
    const int N = 1 << logN;
    treap::Node* S[2 * N];
    int min3[2 * N], max3[2 * N];

    void init()
    {
        memset(S, 0, sizeof S);
        memset(min3, 0x3f, sizeof min3);
        for (int i = 0; i < 2 * N; ++i)
            max3[i] = -INF32;
    }

    void mdf(int v, int vl, int vr, int l, int r, int x, bool rem = false)
    {
        if (l > r || vr < l || r < vl) return;
        if (l <= vl && vr <= r)
        {
            if (!rem)
            {
                if (!task34)
                {
                    treap::add(S[v], x);
                }
                else
                {
                    chkmin(min3[v], x);
                    chkmax(max3[v], x);
                }
            }
            else
            {
                if (!task34)
                    treap::rem(S[v], x);
            }
            return;
        }
        int vm = (vl + vr) >> 1;
        mdf(v << 1, vl, vm, l, r, x, rem);
        mdf(v << 1 | 1, vm + 1, vr, l, r, x, rem);
    }

    pii gt(int pos)
    {
        int min_x = INF32, max_x = -INF32;
        int v = 1, vl = 0, vr = X - 1;
        while (true)
        {
            if (!task34)
            {
                if (S[v])
                {
                    chkmin(min_x, treap::gmin(S[v]));
                    chkmax(max_x, treap::gmax(S[v]));
                }
            }
            else
            {
                chkmin(min_x, min3[v]);
                chkmax(max_x, max3[v]);
            }
            if (vl == vr) break;
            int vm = (vl + vr) >> 1;
            if (pos <= vm)
            {
                v <<= 1;
                vr = vm;
            }
            else
            {
                v <<= 1;
                ++v;
                vl = vm + 1;
            }
        }
        return {min_x, max_x};
    }
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    sgt::init();
    cin >> n >> types >> Q;
    task3 = task34 = true;
    for (int i = 0; i < n; ++i)
    {
        cin >> s[i].x >> s[i].tp >> s[i].t1 >> s[i].t2;
        task34 &= s[i].t1 == 1;
        task3 &= s[i].t2 == 100000000;
        --s[i].tp;
        rx[X++] = s[i].x;
        ev[events++] = {s[i].t1, 0, i};
        ev[events++] = {s[i].t2, 2, i};
    }
    task3 &= task34;
    for (int j = 0; j < Q; ++j)
    {
        cin >> qr[j].x >> qr[j].t;
        qr[j].idx = j;
        rx[X++] = qr[j].x;
        ev[events++] = {qr[j].t, 1, j};
    }
    sort(rx, rx + X);
    X = unique(rx, rx + X) - rx;
//    for (int x = 0; x < X; ++x)
//        cx[rx[x]] = x;

    auto mdf = [&](int xl, int xr, int val, bool rem)
    {
        if (val == -INF32 || val == INF32) return;
        int il = lower_bound(rx, rx + X, xl) - rx;
        int ir = upper_bound(rx, rx + X, xr) - rx - 1;
        if (il > ir) return;
        sgt::mdf(1, 0, X - 1, il, ir, val, rem);
    };

    auto mdf2 = [&](int x1, int x2, bool rem)
    {
        int xm = (x1 + x2) / 2;
        mdf(x1, xm, x1, rem);
        mdf(xm + 1, x2, x2, rem);
    };

    for (int tp = 0; tp < types; ++tp)
    {
        type_on[tp].insert({INF32, 1});
        type_on[tp].insert({-INF32, 1});
    }

    if (task34)
    {
        for (int i = 0; i < n; ++i)
        {
            auto &a = s[i];
            if (!type_on[a.tp].count(a.x))
                type_on[a.tp].insert({a.x, 1});
            else
                ++type_on[a.tp][a.x];
        }
        for (int tp = 0; tp < types; ++tp)
        {
            auto &S = type_on[tp];
            auto x = S.begin();
            auto y = next(x);
            while (y != S.end())
            {
                mdf2(x->fi, y->fi, false);
                x = y;
                y = next(y);
            }
        }
    }
    
    sort(ev, ev + events);
    int active_tp = 0;
    for (int ei = 0; ei < events; ++ei)
    {
        auto &e = ev[ei];
        if (e.tp == 0)
        {
            int i = e.idx;
            auto &a = s[i];
            if (++tp_cnt[a.tp] == 1)
                ++active_tp;
            if (task34) continue;
            auto &S = type_on[a.tp];
            if (S.find(a.x) != S.end())
                ++S[a.x];
            else
            {
                S.insert({a.x, 1}); 
                auto it = S.find(a.x);
                int x1 = prev(it)->fi;
                int x2 = next(it)->fi;
                mdf2(x1, x2, true);
                mdf2(x1, a.x, false);
                mdf2(a.x, x2, false);
            }
        }
        else if (e.tp == 2)
        {
            if (task34 && task3) break;
            int i = e.idx;
            auto &a = s[i];
            if (--tp_cnt[a.tp] == 0)
                --active_tp;
            auto &S = type_on[a.tp];
            if (--S[a.x] == 0)
            {
                auto it = S.find(a.x);
                int x1 = prev(it)->fi;
                int x2 = next(it)->fi;
                S.erase(it);
                mdf2(x1, a.x, true);
                mdf2(a.x, x2, true);
                mdf2(x1, x2, false);
            }
        }
        else
        {
            int j = e.idx;
            auto &q = qr[j];
            if (active_tp < types)
                ans[j] = INF32;
            else
            {
                auto res = sgt::gt(lower_bound(rx, rx + X, q.x) - rx);
                ans[j] = max(labs(q.x - res.fi), labs(q.x - res.se));
            }
        }
    }

    for (int j = 0; j < Q; ++j)
        cout << (ans[j] >= INF32 ? -1 : ans[j]) << '\n';

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize("O3")
      | 
new_home.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
new_home.cpp:3: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
    3 | #pragma gcc target("avx2")
      |

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