Submission #1154918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154918		study__algo	Sparklers (JOI17_sparklers)	C++20	0 / 100	0 ms	468 KiB

sparklers

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

  int n, k, t;
  cin >> n >> k >> t;
  --k;

  vector<int> a(n);
  for (auto& x : a) {
    cin >> x;
  }

  auto check = [&](int x) {
    vector<i64> v(n);
    for (int i = 0; i < n; ++i) {
      v[i] = a[i] - 2LL * x * i * t;
    }
    [[maybe_unused]] const int max_l = int(distance(v.begin(), max_element(v.begin(), next(v.begin(), k + 1))));
    [[maybe_unused]] const int min_r = int(distance(v.begin(), min_element(next(v.begin(), k), v.end())));
    {
      int l = k;
      int best_l = k;
      int r = k;
      int best_r = k;
      while (true) {
        bool done = true;
        while (l > 0 && v[l - 1] >= v[best_r]) {
          done = false;
          l -= 1;
          if (v[best_l] < v[l]) {
            best_l = l;
          }
        }
        while (r < n - 1 && v[best_l] >= v[r + 1]) {
          done = false;
          r += 1;
          if (v[best_r] > v[r]) {
            best_r = r;
          }
        }
        if (done) {
          break;
        }
      }
      if (l > 0 || r < n - 1) {
        return false;
      }
    }
    return true;
    // {
    //   int l = 0;
    //   int best_l = 0;
    //   int r = n - 1;
    //   int best_r = n - 1;
    //   while (true) {
    //     bool done = true;
    //     while (l > 0 && v[l - 1] >= v[best_r]) {
    //       done = false;
    //       l -= 1;
    //       if (v[best_l] < v[l]) {
    //         best_l = l;
    //       }
    //     }
    //     while (r < n - 1 && v[best_l] >= v[r + 1]) {
    //       done = false;
    //       r += 1;
    //       if (v[best_r] > v[r]) {
    //         best_r = r;
    //       }
    //     }
    //     if (done) {
    //       break;
    //     }
    //   }
    //   if (l > 0 || r < n - 1) {
    //     return false;
    //   }
    // }
  };

  int low = -1;
  int high = (int(5E8) + t - 1) / t;
  while (high - low > 1) {
    const int mid = low + (high - low) / 2;
    (check(mid) ? high : low) = mid;
  }

  const int ans = high;
  cout << ans << "\n";

  return 0;
}

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