oj.uz

Submission #73281

# Submission time Handle Problem Language Result Execution time Memory
73281 2018-08-28T06:35:47 Z 강태규(#2268) Circus (Balkan15_CIRCUS) C++11
0 / 100
 98 ms 6520 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];
map<int, int> mp;

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

void update(priority_queue<node> &pq, int x) {
    if (x == -1) return;
    pii r(inf, -1);
    map<int, int>::iterator it;
    it = mp.lower_bound(cp[x] + dp[x]);
    if (it != mp.end())
        r = min(r, pii(it->first - cp[x], it->second));
    it = mp.lower_bound(cp[x] - dp[x] + 1);
    if (it != mp.begin())
        --it, r = min(r, pii(cp[x] - it->first, it->second));
    if (r.second != -1) pq.emplace(r.second, r.first, x);
}

int rt;
void init(int N, int M, int P[]) {
    n = N;
    mx = M;
    for (int i = 0; i < n; ++i) mp[cp[i] = P[i]] = i, dp[i] = -1;
    sort(cp, cp + n);
    mp[cp[n] = mx] = n;
    dp[n] = -1;
    
    priority_queue<node> pq;
    pq.emplace(n, 0, -1);
    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;
        update(pq, x.it);
        update(pq, x.pr);
    }
}

int minLength(int D) {
    int ans = inf;
    for (int i = 0; i <= n; ++i) {
        if (dp[i] <= abs(D - cp[i])) ans = min(ans, abs(D - cp[i]));
    }
    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
0 / 11.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 31.0

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

Subtask #6
0 / 9.0

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