oj.uz

Submission #73263

# Submission time Handle Problem Language Result Execution time Memory
73263 2018-08-28T06:14:45 Z 강태규(#2268) Circus (Balkan15_CIRCUS) C++11
11 / 100
 112 ms 39264 KB 
#include "circus.h"
#include <cstdio>
#include <algorithm>

using namespace std;

int n, mx;
int cp[100000];
int dp[100000];

const int inf = 1e9 + 7;
struct node {
    int l, r, mn;
    node() : l(-1), r(-1) {}
} ns[32 * 100000];

int _alloc() {
    static int tp = 0;
    ns[tp].mn = mx;
    return tp++;
}

void update(int &i, int s, int e, int x, int y, int v) {
    if (e < x || y < s) return;
    if (i == -1) i = _alloc();
    if (x <= s && e <= y) {
        ns[i].mn = min(ns[i].mn, v);
        return;
    }
    int m = (s + e) / 2;
    update(ns[i].l, s, m, x, y, v);
    update(ns[i].r, m + 1, e, x, y, v);
}

int query(int &i, int s, int e, int x) {
    if (i == -1) return mx;
    int ret = ns[i].mn;
    if (s == e) return ret;
    int m = (s + e) / 2;
    if (x <= m) ret = min(ret, query(ns[i].l, s, m, x));
    else ret = min(ret, query(ns[i].r, m + 1, e, x));
    return ret;
}

int rt;
void init(int N, int M, int P[]) {
    n = N;
    mx = M;
    rt = _alloc();
    for (int i = 0; i < n; ++i) cp[i] = P[i];
    sort(cp, cp + n);
    for (int i = n; i--; ) {
        dp[i] = query(rt, 0, mx - 1, cp[i]) - cp[i];
        update(rt, 0, mx - 1, 0, cp[i] - dp[i], cp[i]);
    }
}

int minLength(int D) {
    return query(rt, 0, mx - 1, D) - D;
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 39032 KB Output is correct
2 Correct 112 ms 39264 KB Output is correct
3 Correct 106 ms 39264 KB Output is correct
4 Correct 93 ms 39264 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 39032 KB Output is correct
2 Correct 112 ms 39264 KB Output is correct
3 Correct 106 ms 39264 KB Output is correct
4 Correct 93 ms 39264 KB Output is correct
5 Incorrect 32 ms 39264 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 39032 KB Output is correct
2 Correct 112 ms 39264 KB Output is correct
3 Correct 106 ms 39264 KB Output is correct
4 Correct 93 ms 39264 KB Output is correct
5 Incorrect 32 ms 39264 KB Output isn't correct
6 Halted 0 ms 0 KB -