Submission #625185

#	Time	Username	Problem	Language	Result	Execution time	Memory
625185		EthanKim8683	Circus (Balkan15_CIRCUS)	C++17	11 / 100	78 ms	17044 KiB

circus

#ifndef ETHANKIM8683
#include "circus.h"
#endif
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

using I = int;

/*
Something to note is that jumps may only get
smaller and smaller the closer the performer
gets to the entrance, the inverse is also true.

let a = this rope's distance to the entrance
let b = that rope's distance to the ceiling
let c = that rope's distance to the entrance

Going forward:
`c - a >= b`, therefore `a <= c - b`

Going backward:
`a - c >= b`, therefore `a >= c + b`

The closest rope that satisfies this property
solves the current rope.

Now, keep in mind, a bend (the only time going
backwards is valid) happens, at max, one time.
*/

const I N = 100000;
const I LOGN = 17;
const I MIN = -1e9;
const I MAX = 1e9;

priority_queue<pair<I, I>> que1;
priority_queue<pair<I, I>, vector<pair<I, I>>, greater<pair<I, I>>> que2;
I diss[N];
vector<I> cpss1;
vector<I> cpss2;
I spas1[N + 1][LOGN + 1];
I spas2[N + 1][LOGN + 1];

I cps1(I x) {
  return lower_bound(cpss1.begin(), cpss1.end(), x) - cpss1.begin();
}

I cps2(I x) {
  return upper_bound(cpss2.begin(), cpss2.end(), x) - cpss2.begin() - 1;
}

void asn1(I i, I val) {
  spas1[i][0] = min(spas1[i][0], val);
}

void asn2(I i, I val) {
  spas2[i][0] = max(spas2[i][0], val);
}

void unq1() {
  sort(cpss1.begin(), cpss1.end());
  cpss1.erase(unique(cpss1.begin(), cpss1.end()), cpss1.end());
}

void unq2() {
  sort(cpss2.begin(), cpss2.end());
  cpss2.erase(unique(cpss2.begin(), cpss2.end()), cpss2.end());
}

void bld1() {
  for (I i = 1; i <= LOGN; i++)
    for (I j = 0; j + (1 << (i - 1)) < cpss1.size(); j++)
      spas1[j][i] = min(spas1[j][i - 1], spas1[j + (1 << (i - 1))][i - 1]);
}

void bld2() {
  for (I i = 1; i <= LOGN; i++)
    for (I j = 0; j + (1 << (i - 1)) < cpss2.size(); j++)
      spas2[j][i] = max(spas2[j][i - 1], spas2[j + (1 << (i - 1))][i - 1]);
}

I qry1(I l, I r) {
  const I dis = 31 - __builtin_clz(r - l);
  return min(spas1[l][dis], spas1[r - (1 << dis)][dis]);
}

I qry2(I l, I r) {
  const I dis = 31 - __builtin_clz(r - l);
  return max(spas2[l][dis], spas2[r - (1 << dis)][dis]);
}

void init(I n, I m, I p_arr[]) {
  fill(&spas1[0][0], &spas1[0][0] + sizeof(spas1) / sizeof(I), MAX);
  fill(&spas2[0][0], &spas2[0][0] + sizeof(spas2) / sizeof(I), MIN);
  fill_n(diss, n, MAX);
  sort(p_arr, p_arr + n);
  que1.push({m - 0, m});
  I clo = MAX;
  for (I i = n - 1; i >= 0; i--) {
    const auto p = p_arr[i];
    while (!que1.empty() && p <= que1.top().first) {
      const auto [d, a] = que1.top();
      que1.pop();
      clo = min(clo, a);
    }
    que1.push({p - (diss[i] = min(diss[i], clo - p)), p});
  }
  clo = MIN;
  for (I i = 0; i < n; i++) {
    const auto p = p_arr[i];
    while (!que2.empty() && p >= que2.top().first) {
      const auto [d, a] = que2.top();
      que2.pop();
      clo = max(clo, a);
    }
    que2.push({p + (diss[i] = min(diss[i], p - clo)), p});
  }
  for (I i = 0; i < n; i++) {
    cpss1.push_back(p_arr[i] - diss[i]);
    cpss2.push_back(p_arr[i] + diss[i]);
  }
  cpss1.push_back(m - 0);
  cpss2.push_back(m + 0);
  unq1();
  unq2();
  for (I i = 0; i < n; i++) {
    asn1(cps1(p_arr[i] - diss[i]), p_arr[i]);
    asn2(cps2(p_arr[i] + diss[i]), p_arr[i]);
  }
  asn1(cps1(m - 0), m);
  asn2(cps2(m + 0), m);
  bld1();
  bld2();
}

I minLength(I d) {
  I res = qry1(cps1(d), cpss1.size()) - d;
  const I ind = cps2(d);
  if (ind >= 0)
    res = min(res, d - qry2(0, ind + 1));
  return res;
}

#ifdef ETHANKIM8683
#include <iostream>
#include <cstdio>

I main(void) {
  cin.tie(0)->sync_with_stdio(0);
  I n, m;
  cin >> n >> m;
  static I p[N];
  for (I i = 0; i < n; i++)
    cin >> p[i];
  init(n, m, p);
  while (true) {
    I d = -1;
    cin >> d;
    if (d == -1)
      break;
    printf("%i\n", minLength(d));
  }
  return 0;
}
#endif

Compilation message (stderr)

circus.cpp: In function 'void bld1()':
circus.cpp:75:38: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (I j = 0; j + (1 << (i - 1)) < cpss1.size(); j++)
      |                   ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
circus.cpp: In function 'void bld2()':
circus.cpp:81:38: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (I j = 0; j + (1 << (i - 1)) < cpss2.size(); j++)
      |                   ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
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 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9