oj.uz

Submission #275230

# Submission time Handle Problem Language Result Execution time Memory
275230 2020-08-20T05:00:54 Z 반딧불(#5115) Circus (Balkan15_CIRCUS) C++17
0 / 100
 30 ms 3320 KB 
#include <bits/stdc++.h>
#include "circus.h"

using namespace std;

typedef long long ll;

int n, m;
int arr[100002];
int DP[100002];

vector<pair<int, int> > stk;

void init(int N, int M, int P[]){
    n = N, m = M;
    for(int i=1; i<=n; i++) arr[i] = P[i-1];
    sort(arr+1, arr+n+1);
    arr[++n] = m;

    DP[n] = 0;
    stk.push_back({-m, n});
    for(int i=n-1; i>=1; i--){
        auto it = prev(upper_bound(stk.begin(), stk.end(), make_pair(-arr[i], 0)));
        DP[i] = arr[it->second] - arr[i];

        while(!stk.empty() && -stk.back().first <= arr[i] - DP[i]) stk.pop_back();
        stk.push_back({-(arr[i] - DP[i]), i});
    }

    reverse(stk.begin(), stk.end());
    for(auto &x: stk) x.first *= -1;

//    for(int i=1; i<=n; i++) printf("%d ", DP[i]);
}

int minLength(int x){
    auto it = lower_bound(stk.begin(), stk.end(), make_pair(x, 0));
    return arr[it->second] - x;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
   14 |  long long max_code;
      |            ^~~~~~~~
grader.cpp:16:7: 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:8: 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:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
grader.cpp:23:8: 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -