Submission #1187678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187678		0x34c	Circus (Balkan15_CIRCUS)	C++20	100 / 100	1145 ms	24568 KiB

circus

#include "circus.h"

#define ll long long
#define pii pair<ll, ll>
#include <bits/stdc++.h>

using namespace std;

ll gN, gM;
const ll MAX_N = 1000010, MAX_Q = 1000010;
const ll INF = 1e15;

struct persistent_array
{
private:
    vector<vector<pair<ll, pii>>> arr;
    ll n;
    vector<ll> idxs;

public:
    persistent_array() {}
    void build(ll _n)
    {
        n = _n;
        arr.resize(n);
        idxs.resize(n, n);
    }

    pii get_item(ll idx, ll t)
    {
        ll l = 0, r = arr[idx].size() - 1;
        ll lb = -1;

        while (l <= r)
        {
            ll m = l + (r - l) / 2;
            if (arr[idx][m].first >= t)
            {
                lb = m;
                l = m + 1;
            }
            else
                r = m - 1;
        }

        return arr[idx][lb].second;
    }

    void update_item(ll idx, ll t, pii val)
    {
        arr[idx].push_back({t, val});
        idxs[t] = idx;
    }

    ll get_idx(ll t)
    {
        return idxs[t];
    }
};

ll dist[MAX_N][2], iarr[MAX_N];
ll dp[MAX_N];
persistent_array back_arr, front_arr;

void init(int N, int M, int P[])
{
    gN = N;
    gM = M;

    sort(P, P + N);

    for (ll i = 0; i < N; i++)
    {
        iarr[i] = P[i];
        dist[i][0] = dist[i][1] = INF;
    }
    iarr[N] = M;
    dist[N][0] = dist[N][1] = INF;

    // dijkstra, 0 = left; 1 = right
    dist[N][0] = dist[N][1] = 0;
    priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> q;
    q.push({0, {N, 0}});

    while (!q.empty())
    {
        ll w = q.top().first;
        auto [v, t] = q.top().second;
        q.pop();

        if (dist[v][t] < w)
            continue;

        // go left
        ll lb = upper_bound(iarr, iarr + N + 1, iarr[v] - w) - iarr;
        if (lb != N + 1)
        {
            --lb;
            if (lb == v)
                --lb;

            if (lb >= 0 && dist[lb][0] > iarr[v] - iarr[lb])
            {
                dist[lb][0] = iarr[v] - iarr[lb];
                q.push({dist[lb][0], {lb, 0}});
            }
        }

        // go right
        ll rb = lower_bound(iarr, iarr + N + 1, iarr[v] + w) - iarr;
        if (rb == v)
            rb++;

        if (rb <= N && dist[rb][1] > iarr[rb] - iarr[v])
        {
            dist[rb][1] = iarr[rb] - iarr[v];
            q.push({dist[rb][1], {rb, 1}});
        }

        // continue to the same direction
        if (t == 0 && v - 1 >= 0 && dist[v - 1][0] > w + iarr[v] - iarr[v - 1])
        {
            dist[v - 1][0] = w + iarr[v] - iarr[v - 1];
            q.push({dist[v - 1][0], {v - 1, 0}});
        }

        if (t == 1 && v + 1 <= N && dist[v + 1][1] > w + iarr[v + 1] - iarr[v])
        {
            dist[v + 1][1] = w + iarr[v + 1] - iarr[v];
            q.push({dist[v + 1][1], {v + 1, 1}});
        }
    }

    for (ll i = 0; i <= N; i++)
        dp[i] = min(dist[i][0], dist[i][1]);

    back_arr.build(N + 1);
    front_arr.build(N + 1);

    back_arr.update_item(N, N, {M, M});

    ll idx = N;
    for (ll i = N - 1; i >= 0; i--)
    {
        while (idx <= N && back_arr.get_item(idx, i).first <= P[i] - dp[i])
            idx++;
        --idx;
        back_arr.update_item(idx, i, {P[i] - dp[i], P[i]});
    }

    front_arr.update_item(N, N, {iarr[0] + dp[0], iarr[0]});
    idx = N;

    for (ll i = 1, j = N - 1; i <= N; i++, j--)
    {
        while (idx <= N && front_arr.get_item(idx, j).first >= iarr[i] + dp[i])
            idx++;
        --idx;
        front_arr.update_item(idx, j, {iarr[i] + dp[i], iarr[i]});
    }
}
int minLength(int D)
{
    ll l = 0, r = gN;
    ll lb = gN;

    while (l <= r)
    {
        ll m = l + (r - l) / 2;
        if (iarr[m] >= D)
        {
            lb = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }

    ll i = lb;
    ll idx = back_arr.get_idx(i);
    l = idx;
    r = gN;
    lb = gM;
    while (l <= r)
    {
        ll m = l + (r - l) / 2;
        pii item = back_arr.get_item(m, i);

        if (D <= item.first)
        {
            lb = item.second;
            r = m - 1;
        }
        else
            l = m + 1;
    }

    ll res = lb - D;

    l = 0;
    r = gN;
    lb = -INF;

    while (l <= r)
    {
        ll m = l + (r - l) / 2;
        if (iarr[m] <= D)
        {
            lb = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }

    if (lb == -INF)
        return res;

    i = lb;
    idx = front_arr.get_idx(gN - i);
    l = idx;
    r = gN;
    lb = -INF;
    while (l <= r)
    {
        ll m = l + (r - l) / 2;
        pii item = front_arr.get_item(m, gN - i);

        if (D >= item.first)
        {
            lb = item.second;
            r = m - 1;
        }
        else
            l = m + 1;
    }

    res = min(res, D - lb);
    return res;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d", &P[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 9 / 9
• Subtask 5: 31 / 31
• Subtask 6: 9 / 9