Submission #1187369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187369		0x34c	Circus (Balkan15_CIRCUS)	C++20	0 / 100	31 ms	26944 KiB

circus

#include "circus.h"

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

using namespace std;

int gN, gM;
const int MAX_N = 1000010, MAX_Q = 1000010;
vector<pair<int, pii>> arr[MAX_N];
int indexik[MAX_N];

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

    while (l <= r)
    {
        int 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(int idx, int t, pii val)
{
    arr[idx].push_back({t, val});
}

int dp[MAX_N], iarr[MAX_N];

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

    for (int i = 0; i < N; i++)
        iarr[i] = P[i];

    update_item(N, N, {M, M});
    dp[N] = 0;

    int idx = N;
    indexik[N] = idx;

    for (int i = N - 1; i >= 0; i--)
    {
        int l = idx, r = N;
        int lb = M;
        while (l <= r)
        {
            int m = l + (r - l) / 2;
            pii item = get_item(m, i);

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

        dp[i] = lb - P[i];

        while (get_item(idx, i).first <= P[i] - dp[i])
            idx++;
        --idx;
        update_item(idx, i, {P[i] - dp[i], P[i]});
        indexik[i] = idx;
    }
}
int minLength(int D)
{
    int l = 0, r = gN;
    int lb = gN;

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

    int i = lb;
    int idx = indexik[i];
    l = idx;
    r = gN;
    lb = gM;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        pii item = get_item(m, i);

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

    return lb - D;
}

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: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9