Submission #408820

#	Time	Username	Problem	Language	Result	Execution time	Memory
408820		Mamnoon_Siam	Sparklers (JOI17_sparklers)	C++17	100 / 100	185 ms	9488 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  int n, k; ll t;
  scanf("%d %d %lld", &n, &k, &t);
  vector<ll> X(n+1);
  for(int i = 1; i <= n; ++i) {
    scanf("%lld", &X[i]);
  }
  if(X[n] == 0) {
    puts("0");
    return 0;
  }
  function<bool(ll)> possible = [&](ll s) {
    auto x = X;
    for(int i = 1; i <= n; ++i) {
      x[i] -= 2LL * s * t * i;
    }
    x[0] = LLONG_MAX;
    x.push_back(LLONG_MIN);
    vi pg(n+1), ns(n+1), ng(n+1), ps(n+1);
    vector<ll> pg_min = x, ns_max = x;
    vector<ll> ng_min = x, ps_max = x;
    vector<int> stk = {0};
    for(int i = 1; i <= n; ++i) {
      while(x[stk.back()] < x[i]) {
        pg_min[i] = min(pg_min[i], pg_min[stk.back()]);
        stk.pop_back();
      }
      pg[i] = stk.back();
      stk.push_back(i);
    }
    stk.clear();
    stk = {n+1};
    for(int i = n; i >= 1; --i) {
      while(x[stk.back()] > x[i]) {
        ns_max[i] = max(ns_max[i], ns_max[stk.back()]);
        stk.pop_back();
      }
      ns[i] = stk.back();
      stk.push_back(i);
    }
    stk.clear();
    x[0] = LLONG_MIN, x[n+1] = LLONG_MAX;
    stk = {0};
    for(int i = 1; i <= n; ++i) {
      while(x[stk.back()] >= x[i]) {
        ps_max[i] = max(ps_max[i], ps_max[stk.back()]);
        stk.pop_back();
      }
      ps[i] = stk.back();
      stk.push_back(i);
    }
    stk.clear();
    stk = {n+1};
    for(int i = n; i >= 1; --i) {
      while(x[stk.back()] <= x[i]) {
        ng_min[i] = min(ng_min[i], ng_min[stk.back()]);
        stk.pop_back();
      }
      ng[i] = stk.back();
      stk.push_back(i);
    }
    int l1 = k, r1 = k;
    while(pg[l1] >= 1 or ns[r1] <= n) {
      if(pg[l1] >= 1 and pg_min[l1] >= x[r1])
        l1 = pg[l1];
      else if(ns[r1] <= n and ns_max[r1] <= x[l1])
        r1 = ns[r1];
      else
        return false;
    }
    int l2 = 1, r2 = n;
    while(ng[l2] <= k or ps[r2] >= k) {
      if(ng[l2] <= k and ng_min[l2] >= x[r2])
        l2 = ng[l2];
      else if(ps[r2] >= k and ps_max[r2] <= x[l2])
        r2 = ps[r2];
      else
        return false;
    }
    return l1 == l2 and r1 == r2;
  };
  int lo = 1, hi = 1e9, opt = -1;
  while(lo <= hi) {
    int mid = (lo + hi) >> 1;
    if(possible(mid)) {
      opt = mid;
      hi = mid-1;
    } else {
      lo = mid+1;
    }
  }
  printf("%d\n", opt);
  return 0;
}
/*
* use std::array instead of std::vector, if u can
* overflow?
* array bounds
*/

Compilation message (stderr)

sparklers.cpp: In function 'int main(int, const char**)':
sparklers.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d %d %lld", &n, &k, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%lld", &X[i]);
      |     ~~~~~^~~~~~~~~~~~~~~

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