Submission #375982

#	Time	Username	Problem	Language	Result	Execution time	Memory
375982		usachevd0	New Home (APIO18_new_home)	C++14	100 / 100	4966 ms	765164 KiB

new_home

#pragma gcc optimize("Ofast")
#pragma gcc optimize("O3")
#pragma gcc target("avx2")
#include <bits/stdc++.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(a, n) 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) { return stream << a.fi << ' ' << a.se; }

const int INF32 = 0x3f3f3f3f;
const int N = 300005;
int n, types, Q;

struct shop_t
{
    int x, tp, t1, t2;
} s[N];

struct query_t
{
    int x, t;
} qr[N];
int qord[N], whenq[N], 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, pair<int, pii>> ts[N];

struct ray_t
{
    int x1, x2, w, tp;

    bool operator < (const ray_t &oth) const
    {
        if (x1 != oth.x1) return x1 < oth.x1;
        if (x2 != oth.x2) return x2 < oth.x2;
        if (w != oth.w) return w < oth.w;
        return tp < oth.tp;
    }
};

struct event2_t
{
    int x, tp, val;

    bool operator < (const event2_t& oth) const
    {
        if (x != oth.x) return x < oth.x;
        return tp < oth.tp;
    }
};

struct event3_t
{
    char tp;
    int val;
};

namespace lnk
{
    const int maxV = 60000007;
    int V = 1;
    event3_t val[maxV];
    int nxt[maxV];

    void add(int &i, event3_t x)
    {
        if (V == maxV)
        {
            exit(0);
        }
        val[V] = x;
        nxt[V] = i;
        i = V++;
    }
}

namespace sgt
{
    const int logN = 19;
    const int NN = 1 << logN;
//    vector<event2_t> ev[2][2 * NN];
    int ev[2][2 * NN];

    void add_event(event3_t e, int w, int l, int r)
    {
        for (l += NN, r += NN; l <= r; l >>= 1, r >>= 1)
        {
            if (l & 1)  lnk::add(ev[w][l++], e);
            if (~r & 1) lnk::add(ev[w][r--], e);
        }
    }

    void add_query(event3_t e, int t)
    {
        for (t += NN; t >= 1; t >>= 1)
        {
            lnk::add(ev[0][t], e);
            lnk::add(ev[1][t], e);
        }
    }

    event3_t temp[12 * N];
    void dfs(int v, int vl, int vr)
    {
        {
            int mx = -INF32;
            int sz = 0;
            for (int idx = ev[1][v]; idx; idx = lnk::nxt[idx])
            {
                temp[sz++] = lnk::val[idx];
            }
            reverse(temp, temp + sz);
            for (int i = 0; i < sz; ++i)
            {
                auto &e = temp[i];
                if (e.tp == 0)
                {
                    chkmax(mx, e.val);
                }
                else
                {
                    int j = e.val;
                    auto &q = qr[j];
                    chkmax(ans[j], mx - q.x);
                }
            }
        }
        {
            int mn = INF32;
            for (int idx = ev[0][v]; idx; idx = lnk::nxt[idx])
            {
                auto e = lnk::val[idx];
                if (e.tp == 2)
                {
                    chkmin(mn, e.val);
                }
                else
                {
                    int j = e.val;
                    auto &q = qr[j];
                    chkmax(ans[j], q.x - mn);
                }
            }
        }
        if (vl != vr)
        {
            int vm = (vl + vr) >> 1;
            dfs(v << 1, vl, vm);
            dfs(v << 1 | 1, vm + 1, vr);
        }
    }
}

const int MAXRAYS = 10 * N;
ray_t rays[MAXRAYS];
int rays_t1[MAXRAYS];
int rays_cnt;

pair<event2_t, pii> ep[2 * MAXRAYS];
int ep_sz;

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

    cin >> n >> types >> Q;
    for (int i = 0; i < n; ++i)
    {
        auto &e = s[i];
        cin >> e.x >> e.tp >> e.t1 >> e.t2;
        --e.tp;
        ev[events++] = {e.t1, 0, i};
        ev[events++] = {e.t2, 2, i};
    }
    for (int j = 0; j < Q; ++j)
    {
        auto &q = qr[j];
        cin >> q.x >> q.t;
        ev[events++] = {q.t, 1, j};
    }

    sort(ev, ev + events);
    int T = 0;

    auto add_ray_ev = [&](ray_t ray, int t1, int t2)
    {
        if (t1 <= t2)
        {
            if (ray.w == 0)
            {
                ep[ep_sz++] = {{ray.x2, 2, ray.x1}, {t1, t2}};
            }
            else
            {
                ep[ep_sz++] = {{ray.x1, 0, ray.x2}, {t1, t2}};
            }
        }
    };

    auto add = [&](int x1, int x2, int w, int ri, int tp)
    {
        ray_t ray = {x1, x2, w, tp};
        rays[ri] = ray;
        rays_t1[ri] = T;
    };
    auto add2 = [&](int x1, int x2, int r0, int r1, int tp)
    {
//        cerr << "add2 " << x1 << ' ' << x2 << ' ' << r0 << ' ' << r1 << endl;
        int xm = (x1 + x2) / 2;
        add(x1, xm, 0, r0, tp);
        add(xm + 1, x2, 1, r1, tp);
    };
    auto rem = [&](int ri)
    {   
//        cerr << "rem " << ri << endl;
        add_ray_ev(rays[ri], rays_t1[ri], T - 1);
        rays_t1[ri] = -1;
    };

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

    for (int ei = 0; ei < events; ++ei)
    {
        auto& e = ev[ei];
        if (e.tp == 0)
        {
            int i = e.idx;
            auto &f = s[i];
            auto &S = ts[f.tp];
            if (S.find(f.x) != S.end())
                ++S[f.x].fi;
            else
            {
                S.insert({f.x, {1, {rays_cnt + 1, rays_cnt + 2}}});
                auto Y = S.find(f.x);
                auto Z = next(Y);
                auto X = prev(Y);
                rem(X->se.se.se);
                rem(Z->se.se.fi);
                X->se.se.se = rays_cnt;
                Z->se.se.fi = rays_cnt + 3;
                add2(X->fi, Y->fi, rays_cnt, rays_cnt + 1, f.tp);
                add2(Y->fi, Z->fi, rays_cnt + 2, rays_cnt + 3, f.tp);
                rays_cnt += 4;
                assert(rays_cnt < MAXRAYS);
            }
        }
        else if (e.tp == 2)
        {
            int i = e.idx;
            auto &f = s[i];
            auto &S = ts[f.tp];
            if (--S[f.x].fi == 0)
            {
                auto Y = S.find(f.x);
                auto Z = next(Y);
                auto X = prev(Y);
                rem(X->se.se.se);
                rem(Y->se.se.fi);
                rem(Y->se.se.se);
                rem(Z->se.se.fi);
                add2(X->fi, Z->fi, rays_cnt, rays_cnt + 1, f.tp);
                X->se.se.se = rays_cnt;
                Z->se.se.fi = rays_cnt + 1;
                rays_cnt += 2;
                assert(rays_cnt < MAXRAYS);
                S.erase(Y);
            }
        }
        else
        {
            qord[T] = e.idx;
            whenq[e.idx] = T;
            ++T;
        }
    }
    for (int ri = 0; ri < rays_cnt; ++ri)
    {
        if (rays_t1[ri] == -1) continue;
        add_ray_ev(rays[ri], rays_t1[ri], T - 1);
    }

    for (int j = 0; j < Q; ++j)
    {
        auto &q = qr[j];
        ep[ep_sz++] = {{q.x, 1, j}, {whenq[j], -1}};
    }
    sort(ep, ep + ep_sz);
    debug(clock() * 1.0 / CLOCKS_PER_SEC);
    for (int ep_i = 0; ep_i < ep_sz; ++ep_i)
    {
        auto &el = ep[ep_i];
        auto &e = el.fi;
        int t1 = el.se.fi;
        int t2 = el.se.se;
        if (t2 != -1)
        {
            sgt::add_event({e.tp, e.val}, e.tp == 2 ? 0 : 1, t1, t2);
        }
        else
        {
            sgt::add_query({e.tp, e.val}, t1);
        }
    }
    debug(clock() * 1.0 / CLOCKS_PER_SEC);
    fill(ans, ans + Q, -INF32);
    sgt::dfs(1, 0, sgt::NN - 1);
    for (int j = 0; j < Q; ++j)
        cout << (ans[j] >= INF32 / 2 ? -1 : ans[j]) << '\n';
    debug(clock() * 1.0 / CLOCKS_PER_SEC);

    return 0;
}

Compilation message (stderr)

new_home.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
new_home.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      | 
new_home.cpp:3: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
    3 | #pragma gcc target("avx2")
      | 
new_home.cpp: In function 'int main()':
new_home.cpp:29:24: warning: statement has no effect [-Wunused-value]
   29 |     #define debug(...) 1337
      |                        ^~~~
new_home.cpp:336:5: note: in expansion of macro 'debug'
  336 |     debug(clock() * 1.0 / CLOCKS_PER_SEC);
      |     ^~~~~
new_home.cpp:345:31: warning: narrowing conversion of 'e.event2_t::tp' from 'int' to 'char' [-Wnarrowing]
  345 |             sgt::add_event({e.tp, e.val}, e.tp == 2 ? 0 : 1, t1, t2);
      |                             ~~^~
new_home.cpp:349:31: warning: narrowing conversion of 'e.event2_t::tp' from 'int' to 'char' [-Wnarrowing]
  349 |             sgt::add_query({e.tp, e.val}, t1);
      |                             ~~^~
new_home.cpp:29:24: warning: statement has no effect [-Wunused-value]
   29 |     #define debug(...) 1337
      |                        ^~~~
new_home.cpp:352:5: note: in expansion of macro 'debug'
  352 |     debug(clock() * 1.0 / CLOCKS_PER_SEC);
      |     ^~~~~
new_home.cpp:29:24: warning: statement has no effect [-Wunused-value]
   29 |     #define debug(...) 1337
      |                        ^~~~
new_home.cpp:357:5: note: in expansion of macro 'debug'
  357 |     debug(clock() * 1.0 / CLOCKS_PER_SEC);
      |     ^~~~~

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