oj.uz

답안 #73301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73301 2018-08-28T06:58:50 Z 강태규(#2268) Circus (Balkan15_CIRCUS) C++11
60 / 100
 1387 ms 92380 KB 
#include "circus.h"
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;
typedef pair<int, int> pii;

const int inf = 1e9 + 7;
int n, mx;
int cp[100001];
int dp[100001];
int vis[100001];

struct node {
    int it, cs;
    node(int i, int c) : it(i), cs(c) {}
    bool operator<(const node &p) const {
        return cs > p.cs;
    }
};

void update(priority_queue<node> &pq, int x) {
    for (int i = 0; i <= n; ++i) {
        if (vis[i]) continue;
        if (abs(cp[i] - cp[x]) < dp[x]) continue;
        pq.emplace(i, abs(cp[i] - cp[x]));
    }
}

struct segnode {
    int l, r, mn;
    segnode() : l(-1), r(-1) {}
} ns[2 * 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 rt1, rt2;
void init(int N, int M, int P[]) {
    n = N;
    mx = M;
    rt1 = _alloc(); rt2 = _alloc();
    for (int i = 0; i < n; ++i) cp[i] = P[i];
    sort(cp, cp + n);
    cp[n] = mx;
    
    if (n > 2000) {
        for (int i = n; i--; ) {
            dp[i] = query(rt1, 0, mx, cp[i]) - cp[i];
            update(rt1, 0, mx, 0, cp[i] - dp[i], cp[i]);
        }
        return;
    }
    
    priority_queue<node> pq;
    update(pq, n);
    while (!pq.empty()) {
        node x = pq.top(); pq.pop();
        if (vis[x.it]) continue;
        vis[x.it] = 1;
        dp[x.it] = x.cs;
        update(pq, x.it);
    }
    
    for (int i = 0; i <= n; ++i) {
        update(rt1, 0, mx, 0, cp[i] - dp[i], cp[i]);
        update(rt2, 0, mx, cp[i] + dp[i], mx, -cp[i]);
    }
}

int minLength(int D) {
    int ans = min(query(rt1, 0, mx, D) - D, D + query(rt2, 0, mx, D));
    return ans;
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 76628 KB Output is correct
2 Correct 136 ms 76788 KB Output is correct
3 Correct 130 ms 76788 KB Output is correct
4 Correct 121 ms 76788 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 76788 KB Output is correct
2 Correct 64 ms 76788 KB Output is correct
3 Correct 62 ms 76788 KB Output is correct
4 Correct 67 ms 76788 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 76788 KB Output is correct
2 Correct 64 ms 76788 KB Output is correct
3 Correct 62 ms 76788 KB Output is correct
4 Correct 67 ms 76788 KB Output is correct
5 Correct 553 ms 92288 KB Output is correct
6 Correct 541 ms 92364 KB Output is correct
7 Correct 588 ms 92364 KB Output is correct
8 Correct 596 ms 92364 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 76788 KB Output is correct
2 Correct 64 ms 76788 KB Output is correct
3 Correct 62 ms 76788 KB Output is correct
4 Correct 67 ms 76788 KB Output is correct
5 Correct 553 ms 92288 KB Output is correct
6 Correct 541 ms 92364 KB Output is correct
7 Correct 588 ms 92364 KB Output is correct
8 Correct 596 ms 92364 KB Output is correct
9 Correct 1298 ms 92364 KB Output is correct
10 Correct 1193 ms 92364 KB Output is correct
11 Correct 1204 ms 92380 KB Output is correct
12 Correct 1387 ms 92380 KB Output is correct

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 76628 KB Output is correct
2 Correct 136 ms 76788 KB Output is correct
3 Correct 130 ms 76788 KB Output is correct
4 Correct 121 ms 76788 KB Output is correct
5 Correct 65 ms 76788 KB Output is correct
6 Correct 64 ms 76788 KB Output is correct
7 Correct 62 ms 76788 KB Output is correct
8 Correct 67 ms 76788 KB Output is correct
9 Correct 553 ms 92288 KB Output is correct
10 Correct 541 ms 92364 KB Output is correct
11 Correct 588 ms 92364 KB Output is correct
12 Correct 596 ms 92364 KB Output is correct
13 Incorrect 153 ms 92380 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 76628 KB Output is correct
2 Correct 136 ms 76788 KB Output is correct
3 Correct 130 ms 76788 KB Output is correct
4 Correct 121 ms 76788 KB Output is correct
5 Correct 65 ms 76788 KB Output is correct
6 Correct 64 ms 76788 KB Output is correct
7 Correct 62 ms 76788 KB Output is correct
8 Correct 67 ms 76788 KB Output is correct
9 Correct 553 ms 92288 KB Output is correct
10 Correct 541 ms 92364 KB Output is correct
11 Correct 588 ms 92364 KB Output is correct
12 Correct 596 ms 92364 KB Output is correct
13 Correct 1298 ms 92364 KB Output is correct
14 Correct 1193 ms 92364 KB Output is correct
15 Correct 1204 ms 92380 KB Output is correct
16 Correct 1387 ms 92380 KB Output is correct
17 Incorrect 153 ms 92380 KB Output isn't correct
18 Halted 0 ms 0 KB -