Submission #1043916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043916		juicy	Sparklers (JOI17_sparklers)	C++17	100 / 100	51 ms	3716 KiB

sparklers

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n, k, t;
int x[N];

bool reach(vector<long long> &lt, vector<long long> &rt) {
  if (lt[0] < rt[0]) {
    return 0;
  }
  array<int, 2> l{}, r{};
  bool chg = 1;
  while (chg) {
    chg = 0;
    while (l[0] + 1 < lt.size() && lt[l[0] + 1] >= rt[r[1]]) {
      ++l[0];
      chg = 1;
      if (lt[l[0]] >= lt[l[1]]) {
        l[1] = l[0];
      }
    }
    while (r[0] + 1 < rt.size() && rt[r[0] + 1] <= lt[l[1]]) {
      ++r[0];
      chg = 1;
      if (rt[r[0]] <= rt[r[1]]) {
        r[1] = r[0];
      }
    }
  }
  return l[0] == lt.size() - 1 && r[0] == rt.size() - 1;
}

bool check(int s) {
  vector<long long> lt, rt;
  for (int i = k; i > 0; --i) {
    lt.push_back(x[i] - (long long) 2 * s * i * t);
  }
  for (int i = k; i <= n; ++i) {
    rt.push_back(x[i] - (long long) 2 * s * i * t);
  }
  if (!reach(lt, rt)) {
    return 0;
  }
  reverse(lt.begin(), lt.end());
  reverse(rt.begin(), rt.end());
  return reach(lt, rt);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k >> t;
  for (int i = 1; i <= n; ++i) {
    cin >> x[i];
  }
  int l = 0, r = 1e9, res = r;
  while (l <= r) {
    int md = (l + r) / 2;
    if (check(md)) {
      res = md;
      r = md - 1;
    } else {
      l = md + 1;
    }
  }
  cout << res;
  return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'bool reach(std::vector<long long int>&, std::vector<long long int>&)':
sparklers.cpp:24:21: warning: comparison of integer expressions of different signedness: 'std::array<int, 2>::value_type' {aka 'int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while (l[0] + 1 < lt.size() && lt[l[0] + 1] >= rt[r[1]]) {
sparklers.cpp:31:21: warning: comparison of integer expressions of different signedness: 'std::array<int, 2>::value_type' {aka 'int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while (r[0] + 1 < rt.size() && rt[r[0] + 1] <= lt[l[1]]) {
sparklers.cpp:39:15: warning: comparison of integer expressions of different signedness: 'std::array<int, 2>::value_type' {aka 'int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   return l[0] == lt.size() - 1 && r[0] == rt.size() - 1;
sparklers.cpp:39:40: warning: comparison of integer expressions of different signedness: 'std::array<int, 2>::value_type' {aka 'int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   return l[0] == lt.size() - 1 && r[0] == rt.size() - 1;

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50