oj.uz

Submission #433383

# Submission time Handle Problem Language Result Execution time Memory
433383 2021-06-19T16:38:33 Z ngpin04 Circus (Balkan15_CIRCUS) C++14
11 / 100
 164 ms 6708 KB 
#include <bits/stdc++.h>
#include "circus.h"
//#include "grader.cpp"
#define fi first
#define se second
#define mp make_pair		
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
const int Nmax = 1e5 + 5; 	
const int oo = 1e9;

vector <int> a;
vector <int> fval, gval;

int mx[Nmax << 2];
int mn[Nmax << 2];

int d[Nmax][2];
int dp[Nmax];
int n,m;

void solve() {
  priority_queue <pair <int, pair <int, int>>> heap;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j < 2; j++)
      d[i][j] = oo;
  d[n][0] = 0;
  heap.push(mp(0, mp(n, 0)));
  while (heap.size()) {
    int cur = -heap.top().fi;
    int i = heap.top().se.fi;
    int dir = heap.top().se.se;
    heap.pop();
    if (d[i][dir] != cur)
      continue;
    int j = i + ((dir == 0) ? -1 : 1);
    if (j >= 0 && j <= n && mini(d[j][dir], cur + abs(a[i] - a[j]))) 
      heap.push(mp(-d[j][dir], mp(j, dir)));

    j = lower_bound(a.begin(), a.end(), a[i] + cur) - a.begin();
    if (j <= n && mini(d[j][1], a[j] - a[i]))
      heap.push(mp(-d[j][1], mp(j, 1)));

    j = upper_bound(a.begin(), a.end(), a[i] - cur) - a.begin() - 1;
    if (j >= 0 && mini(d[j][0], a[i] - a[j]))
      heap.push(mp(-d[j][0], mp(j, 0)));
  }

  for (int i = 0; i <= n; i++) {
    dp[i] = min(d[i][0], d[i][1]);
    // cerr << dp[i] << " \n"[i == n];
  }
}

void update(int id, int l, int r, int pos, pair <int, int> val) {
  if (l > pos || r < pos)
    return;
  if (l == r)
    return (void) (mini(mn[id], val.fi), maxi(mx[id], val.se));
  int mid = (l + r) >> 1;
  update(id << 1, l, mid, pos, val);
  update(id << 1 | 1, mid + 1, r, pos, val);
  mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
  mn[id] = min(mn[id << 1], mn[id << 1 | 1]); 
}

pair <int, int> get(int id, int l, int r, int u, int v) {
  if (l > v || r < u)
    return mp(oo, -oo);
  if (l >= u && r <= v)
    return mp(mn[id], mx[id]);
  int mid = (l + r) >> 1;
  pair <int, int> lnode = get(id << 1, l, mid, u, v);
  pair <int, int> rnode = get(id << 1 | 1, mid + 1, r, u, v);
  return mp(min(lnode.fi, rnode.fi), max(lnode.se, rnode.se));
}

void init(int N, int M, int P[]) {
  n = N;
  m = M;
  for (int i = 0; i < n; i++)
    a.push_back(P[i]);
  a.push_back(M);
  sort(a.begin(), a.end());
  solve();

  for (int i = 0; i <= n; i++) {
    fval.push_back(a[i] - dp[i]);
    gval.push_back(a[i] + dp[i]);
  }
  sort(fval.begin(), fval.end());
  fval.resize(unique(fval.begin(), fval.end()) - fval.begin());

  sort(gval.begin(), gval.end());
  gval.resize(unique(gval.begin(), gval.end()) - gval.begin());

  for (int i = 1; i <= ((n + 1) << 2); i++)
    mn[i] = oo, mx[i] = -oo;

  for (int i = 0; i <= n; i++) {
    int pos, val;
    val = a[i] - dp[i];
    pos = lower_bound(fval.begin(), fval.end(), val) - fval.begin();
    update(1, 0, n, pos, mp(a[i], -oo));

    val = a[i] = dp[i];
    pos = lower_bound(gval.begin(), gval.end(), val) - gval.begin();
    update(1, 0, n, pos, mp(oo, a[i]));
  }
}

int minLength(int x) {
  int pos;
  int res = oo;
  pos = lower_bound(fval.begin(), fval.end(), x) - fval.begin();
  res = get(1, 0, n, pos, n).fi - x;

  pos = upper_bound(gval.begin(), gval.end(), x) - gval.begin() - 1;
  if (pos >= 0) 
    mini(res, x - get(1, 0, n, 0, pos).se);

  return res;	
}

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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 6596 KB Output is correct
2 Correct 164 ms 6552 KB Output is correct
3 Correct 150 ms 6708 KB Output is correct
4 Correct 149 ms 6628 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 204 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 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 6596 KB Output is correct
2 Correct 164 ms 6552 KB Output is correct
3 Correct 150 ms 6708 KB Output is correct
4 Correct 149 ms 6628 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 6596 KB Output is correct
2 Correct 164 ms 6552 KB Output is correct
3 Correct 150 ms 6708 KB Output is correct
4 Correct 149 ms 6628 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -