Submission #625276

#	Time	Username	Problem	Language	Result	Execution time	Memory
625276		EthanKim8683	Circus (Balkan15_CIRCUS)	C++17	0 / 100	127 ms	7648 KiB

circus

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

using namespace std;

using I = int;

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

vector<I> unqs;
map<I, I> unvs;
vector<I> cpss1;
vector<I> cpss2;
priority_queue<pair<I, I>, vector<pair<I, I>>, greater<pair<I, I>>> que;
I diss[N + 1];
I ps1[N + 1];
I ps2[N + 1];

void add(I dis, I a) {
  if (dis < diss[a]) {
    diss[a] = dis;
    que.push({dis, a});
  }
}

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

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

void unq3() {
  sort(cpss2.begin(), cpss2.end());
  cpss2.erase(unique(cpss2.begin(), cpss2.end()), cpss2.end());
}
 
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 init(I n, I m, I p_arr[]) {
  for (I i = 0; i < n; i++)
    unqs.push_back(p_arr[i]);
  unq1();
  fill_n(diss, unqs.size(), MAX);
  for (I i = 0; i < unqs.size(); i++)
    unvs.insert({unqs[i], i});
  add(m - unqs.back(), unqs.size() - 1);
  while (!que.empty() && !unvs.empty()) {
    const auto [dis, a] = que.top();
    que.pop();
    if (dis != diss[a])
      continue;
    const I p1 = unqs[a];
    unvs.erase(p1);
    if (!unvs.empty()) {
      auto it = unvs.upper_bound(p1);
      if (it != unvs.end()) {
        const auto [p2, b] = *it;
        I dis = p2 - p1;
        if (dis >= diss[a])
          add(dis, b);
      }
      if (it-- != unvs.begin()) {
        const auto [p2, b] = *it;
        I dis = p1 - p2;
        if (dis >= diss[a])
          add(dis, b);
      }
      auto upp_it = unvs.lower_bound(p1 + dis);
      auto low_it = unvs.upper_bound(p1 - dis);
      if (upp_it != unvs.end())
        add(upp_it->first - p1, upp_it->second);
      if (low_it-- != unvs.begin())
        add(p1 - low_it->first, low_it->second);
    }
  }
  for (I i = 0; i < unqs.size(); i++) {
    cpss1.push_back(unqs[i] - diss[i]);
    cpss2.push_back(unqs[i] + diss[i]);
  }
  unq2();
  unq3();
  fill_n(ps1, cpss1.size(), MAX);
  fill_n(ps2, cpss2.size(), MIN);
  for (I i = 0; i < unqs.size(); i++) {
    const I low = cps1(unqs[i] - diss[i]);
    const I upp = cps2(unqs[i] + diss[i]);
    ps1[low] = min(ps1[low], unqs[i]);
    ps2[upp] = max(ps2[upp], unqs[i]);
  }
  for (I i = cpss1.size() - 1; i - 1 >= 0; i--)
    ps1[i - 1] = min(ps1[i - 1], ps1[i]);
  for (I i = 0; i + 1 < cpss2.size(); i++)
    ps2[i + 1] = max(ps2[i + 1], ps2[i]);
}

I minLength(I d) {
  I res = MAX;
  const I upp = cps1(d);
  const I low = cps2(d);
  if (upp < cpss1.size())
    res = min(res, ps1[upp] - d);
  if (low >= 0)
    res = min(res, d - ps2[low]);
  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 init(I, I, I*)':
circus.cpp:63:19: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (I i = 0; i < unqs.size(); i++)
      |                 ~~^~~~~~~~~~~~~
circus.cpp:95:19: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for (I i = 0; i < unqs.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
circus.cpp:103:19: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for (I i = 0; i < unqs.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
circus.cpp:111:23: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for (I i = 0; i + 1 < cpss2.size(); i++)
      |                 ~~~~~~^~~~~~~~~~~~~~
circus.cpp: In function 'I minLength(I)':
circus.cpp:119:11: warning: comparison of integer expressions of different signedness: 'const I' {aka 'const int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   if (upp < cpss1.size())
      |       ~~~~^~~~~~~~~~~~~~
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: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9