Submission #581930

#	Time	Username	Problem	Language	Result	Execution time	Memory
581930		AlexLuchianov	Sparklers (JOI17_sparklers)	C++14	100 / 100	198 ms	9452 KiB

sparklers

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;

int const nmax = 200000;
int const inf = 1000000000;
int v[5 + nmax];
ll arr[2][5 + nmax];

ll prefmin[5 + nmax], suffmin[5 + nmax];
ll prefmax[5 + nmax], suffmax[5 + nmax];

bool solve(int n, int k, int t, int speed) {
  ll base = speed * t * 2LL;
  int ptr = 0, ptr2 = 0;
  arr[0][++ptr] = 0;
  arr[1][++ptr2] = 0;
  for(int i = k - 1; 1 <= i; i--) {
    arr[0][++ptr] = -(v[i + 1] - v[i]);
    arr[0][++ptr] = base;
  }
  
  for(int i = k + 1; i <= n; i++) {
    arr[1][++ptr2] = -(v[i] - v[i - 1]);
    arr[1][++ptr2] = base;
  }
  
  for(int i = 1; i <= ptr; i++)
    arr[0][i] += arr[0][i - 1];
  for(int i = 1; i <= ptr2; i++)
    arr[1][i] += arr[1][i - 1];
  
  /*
  std::cout << "Visual Map:\n";
  for(int i = 1; i <= ptr; i++) {
    for(int j = 1; j <= ptr2; j++)
      std::cout << (0 <= (base + arr[0][i] + arr[1][j]));
    std::cout << '\n';
  }
  */

  int smax = 1;
  for(int i = 1;i <= ptr; i++)
    if(arr[0][smax] < arr[0][i])
      smax = i;
  
  std::vector<int> stLeft, stRight;
  stLeft.push_back(1);
  for(int i = 2; i <= smax; i++)
    if(arr[0][stLeft.back()] <= arr[0][i])
      stLeft.push_back(i);
  stRight.push_back(ptr);
  for(int i = ptr - 1; smax <= i; i--)
    if(arr[0][stRight.back()] <= arr[0][i])
      stRight.push_back(i);
  
  for(int i = 1; i <= ptr2; i++) { 
    suffmin[i] = prefmin[i] = arr[1][i];
    suffmax[i] = prefmax[i] = arr[1][i];
  }

  for(int i = 2;i <= ptr2; i++) {
    prefmin[i] = std::min(prefmin[i], prefmin[i - 1]);
    prefmax[i] = std::max(prefmax[i], prefmax[i - 1]);
  }

  for(int i = ptr2 - 1; 1 <= i; i--) {
    suffmin[i] = std::min(suffmin[i], suffmin[i + 1]);
    suffmax[i] = std::max(suffmax[i], suffmax[i + 1]);
  }
  
  if(prefmin[ptr2] + arr[0][smax] + base < 0)
    return 0;
  
  auto findPointUpper = [&](int id) {
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2)
      if(x + jump <= ptr2 && 0 <= prefmin[x + jump] + arr[0][id] + base)
        x += jump;
    return x;
  };
  
  auto findPointLower = [&](int id) {
    int x = ptr2 + 1;
    for(int jump = (1 << 20); 0 < jump; jump /= 2)
      if(1 <= x - jump && 0 <= suffmin[x - jump] + arr[0][id] + base)
        x -= jump;
    return x;
  };
  
  auto rangeMin = [&](int x, int y) {
    ll valmin = arr[0][x];
    for(int i = x;i <= y; i++)
      valmin = std::min(valmin, arr[0][i]);
    return valmin;
  };

  for(int i = 1; i < stLeft.size(); i++) {
    int lim = findPointUpper(stLeft[i - 1]);
    if(lim < 1)
      return 0;
    if(rangeMin(stLeft[i - 1], stLeft[i]) + base + prefmax[lim] < 0)
      return 0;
  }
  
  for(int i = 1; i < stRight.size(); i++) {
    int lim = findPointLower(stRight[i - 1]);
    if(ptr2 < lim)
      return 0;
    if(rangeMin(stRight[i], stRight[i - 1]) + base + suffmax[lim] < 0)
      return 0;
  }
  return 1;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, k, t;
  std::cin >> n >> k >> t;
  

  for(int i = 1; i <= n; i++)
    std::cin >> v[i];
  int speed = -1;
  for(int jump = (1 << 30); 0 < jump; jump /= 2)
    if((speed + jump) <= inf / t && solve(n, k, t, speed + jump) == 0)
      speed += jump;
  std::cout << speed + 1 << '\n';
  return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'bool solve(int, int, int, int)':
sparklers.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i = 1; i < stLeft.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
sparklers.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int i = 1; i < stRight.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

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