Submission #864717

#	Time	Username	Problem	Language	Result	Execution time	Memory
864717		manizare	Sparklers (JOI17_sparklers)	C++14	0 / 100	1 ms	8540 KiB

sparklers

#include <bits/stdc++.h> 
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define Pii pair< pii , pii >
#define int long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 6e5 + 10 , sq = 3 , maxq = 1e7 + 1 ,  inf = 1e18 + 10 , mod= 998244353 ,lg = 20 ;
int n ,t , k;
vector <int> a , b ;
int x[maxn] ; 
int pa[maxn] , pb[maxn] , ra[maxn] , rb[maxn]  ,MA[maxn] , MB[maxn] ; 

int ma(int x){
  if(MA[x] != 1)return MA[x] ;
  int mn = 0 ;
  for(int i = x+1 ; i < ra[x] ; i++){
    mn= min(mn , pa[i] - pa[x]) ;
  }
  MA[x] = mn ; 
  return mn ;
}
int mb(int x){
  if(MB[x] != 1)return MB[x] ;
  int mn = 0 ;
  for(int i = x+1 ; i < rb[x] ; i++){
    mn= min(mn , pb[i] - pb[x]) ;
  }
  MB[x] = mn ; 
  return mn ;
}

int sl(){
  int n  =a.size() - 1, m = b.size()-1 ; 
  for(int i =  1 ; i <= n ; i++){
    pa[i] = pa[i-1] + a[i] ;
    MA[i] = 1 ;
  }
  for(int i = 1; i <= m ; i++){
    pb[i] = pb[i-1] + b[i];
    MB[i] = 1 ;
  }
  vector <int> va,  vb ;
  for(int i =n  ; i>= 0; i--){
    while(va.size() && pa[va.back()] < pa[i])va.pop_back() ; 
    if(va.size() == 0)ra[i] = -1 ;
    else ra[i] = va.back() ;
    va.pb(i);
  }
  for(int i = m  ; i>= 0; i--){
    while(vb.size() && pb[vb.back()] < pb[i])vb.pop_back() ; 
    if(vb.size() == 0)rb[i] = -1 ;
    else rb[i] = vb.back() ;
    vb.pb(i);
  }
  int id1 = 0, id2 =0 , sm = 0;
  ra[n+1] = rb[m+1] = -1 ; 
  while(1){
    if(id1 == n && id2 == m)break ;
    int lid1 = id1 , lid2 = id2 ;
    if(ra[id1] == -1 && rb[id2] == -1){
      if(id1!=n && ra[id1] == -1)id1++;
      if(id2!=m && rb[id2] == -1)id2++;
      continue ;
    }
    if(ra[id1] != -1 && pa[id1]+pb[id2]+ma(id1) >= 0){
      id1 = ra[id1] ;
      continue ;
    }
    if(rb[id2] != -1 && pa[id1]+pb[id2]+mb(id2) >= 0){
      id2 = rb[id2] ;
      continue ;
    }
    if(id1 == lid1 && id2 == lid2)return 0 ;
  }
  return 1 ; 
}
 
bool ch(int z){
  if(2*z*t >= 1e9)return 1; 
  a.clear();b.clear();
  a.pb(0);
  b.pb(0) ;
  a.pb(t*2*z); 
  for(int i = k+1; i <= n ; i++){
    a.pb(-(x[i] - x[i-1]));
    a.pb(t*2*z) ;
  }
  for(int i = k-1 ; i >= 1; i--){
    b.pb(-(x[i+1] - x[i]));
    b.pb(t*2*z) ;
  }
  return sl() ;
}
 
signed main() {
  ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
 
  cin >> n >> k >> t ;
  for(int i = 1; i <= n ; i++){
    cin >> x[i] ;
  }
  int l = 0 , r = 1e9 ; 
  while(r-l>1){
    int mid = (l+r)/2 ;
    if(ch(mid) == 1)r= mid ;
    else l = mid ;
  }
  cout << r << "\n";
}
/*
 
*/

Compilation message (stderr)

sparklers.cpp: In function 'long long int sl()':
sparklers.cpp:61:25: warning: unused variable 'sm' [-Wunused-variable]
   61 |   int id1 = 0, id2 =0 , sm = 0;
      |                         ^~

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