oj.uz

답안 #73397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73397 2018-08-28T08:16:11 Z 강태규(#2268) Circus (Balkan15_CIRCUS) C++11
11 / 100
 379 ms 82004 KB 
#include "circus.h"
#include <cstdio>
#include <cstdlib>
#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];
map<int, int> mp;

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

struct segnode {
    int l, r, mn;
    segnode() : l(-1), r(-1) {}
} ns[2 * 32 * 100000];

int _alloc() {
    static int tp = 0;
    ns[tp].mn = inf;
    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 inf;
    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;

int ls[100001];
int rs[100001];
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;
    
    for (int i = 0; i <= n; ++i) mp[cp[i]] = i, ls[i] = -inf, rs[i] = inf;
    
    priority_queue<node> pq;
    pq.emplace(n, 0);
    while (!pq.empty()) {
        node x = pq.top(); pq.pop();
        if (vis[x.it]) continue;
        mp.erase(cp[x.it]);
        vis[x.it] = 1;
        dp[x.it] = x.cs;
        
        map<int, int>::iterator it;
        it = mp.lower_bound(cp[x.it] + 1);
        if (it != mp.end()) {
            ls[it->second] = max(ls[it->second], ls[x.it]);
            if (ls[it->second] != -inf)
                pq.emplace(it->second, cp[it->second] - ls[it->second]);
        }
        it = mp.lower_bound(cp[x.it]);
        if (it != mp.begin()) {
            --it;
            rs[it->second] = min(rs[it->second], rs[x.it]);
            if (rs[it->second] != inf)
                pq.emplace(it->second, rs[it->second] - cp[it->second]);
        }
        
        it = mp.lower_bound(cp[x.it] + dp[x.it]);
        if (it != mp.end()) {
            ls[it->second] = max(ls[it->second], cp[x.it]);
            pq.emplace(it->second, cp[it->second] - cp[x.it]);
        }
        it = mp.lower_bound(cp[x.it] - dp[x.it] + 1);
        if (it != mp.begin()) {
            --it;
            rs[it->second] = min(rs[it->second], cp[x.it]);
            pq.emplace(it->second, cp[x.it] - cp[it->second]);
        }
    }
    
    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) {
    return min(query(rt1, 0, mx, D) - D, query(rt2, 0, mx, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 81848 KB Output is correct
2 Correct 377 ms 81848 KB Output is correct
3 Correct 305 ms 81988 KB Output is correct
4 Correct 317 ms 82004 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 82004 KB Output is correct
2 Correct 69 ms 82004 KB Output is correct
3 Incorrect 71 ms 82004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 82004 KB Output is correct
2 Correct 69 ms 82004 KB Output is correct
3 Incorrect 71 ms 82004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 82004 KB Output is correct
2 Correct 69 ms 82004 KB Output is correct
3 Incorrect 71 ms 82004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 81848 KB Output is correct
2 Correct 377 ms 81848 KB Output is correct
3 Correct 305 ms 81988 KB Output is correct
4 Correct 317 ms 82004 KB Output is correct
5 Correct 58 ms 82004 KB Output is correct
6 Correct 69 ms 82004 KB Output is correct
7 Incorrect 71 ms 82004 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 81848 KB Output is correct
2 Correct 377 ms 81848 KB Output is correct
3 Correct 305 ms 81988 KB Output is correct
4 Correct 317 ms 82004 KB Output is correct
5 Correct 58 ms 82004 KB Output is correct
6 Correct 69 ms 82004 KB Output is correct
7 Incorrect 71 ms 82004 KB Output isn't correct
8 Halted 0 ms 0 KB -