Submission #999321

#	Time	Username	Problem	Language	Result	Execution time	Memory
999321		AdamGS	Sparklers (JOI17_sparklers)	C++17	100 / 100	119 ms	11340 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=1e5+7;
ll T[LIM], n, k, t;
vector<ll>A, B;
vector<pair<ll,ll>>calc(vector<pair<ll,ll>>T) {
  ll m=T.size()-1;
  vector<pair<ll,ll>>P;
  for(int i=(int)T.size()-1; i>=0; --i) {
    pair<ll,ll>x={max(0ll, T[i].st), T[i].nd-T[i].st};
    while(P.size()>0 && x.nd<0) {
      if(P.back().nd<0) break;
      pair<ll,ll>y={max(x.st, P.back().st-x.nd), x.nd+P.back().nd};
      P.pop_back();
      x=y;
    }
    P.pb(x);
  }
  reverse(all(P));
  return P;
}
bool check(ll x) {
  vector<pair<ll,ll>>X, Y;
  for(auto i : A) X.pb({i, 2*x*t});
  for(auto i : B) Y.pb({i, 2*x*t});
  vector<pair<ll,ll>>P=calc(X), Q=calc(Y);
  ll l1=0, l2=0, akt=2*x*t;
  while(l1<P.size() && l2<Q.size()) {
    if(P[l1].st>akt && Q[l2].st>akt) return false;
    if(P[l1].st<=akt && P[l1].nd>=0) {
      akt+=P[l1].nd;
      ++l1;
    } else if(Q[l2].st<=akt && Q[l2].nd>=0) {
      akt+=Q[l2].nd;
      ++l2;
    } else break;
  }
  if(l1<P.size() && P[l1].st>akt && P[l1].nd>0) return false;
  if(l2<Q.size() && Q[l2].st>akt && Q[l2].nd>0) return false;
  vector<ll>prefp, prefq;
  prefp.pb(0); prefq.pb(0);
  for(int i=l1; i<P.size(); ++i) prefp.pb(prefp.back()+P[i].nd);
  for(int i=l2; i<Q.size(); ++i) prefq.pb(prefq.back()+Q[i].nd);
  int a=prefp.size(), b=prefq.size();
  vector<ll>kiedyp(a), kiedyq(b);
  rep(i, a-1) if(akt+prefp[a-i-2]<P[P.size()-i-1].st) return false;
  rep(i, b-1) if(akt+prefq[b-i-2]<Q[Q.size()-i-1].st) return false;
  int l=b-1;
  rep(i, a-1) {
    while(akt+prefp[a-i-2]+prefq[l]<P[P.size()-i-1].st) --l;
    kiedyp[a-i-1]=l;
  }
  l=a-1;
  rep(i, b-1) {
    while(akt+prefq[b-i-2]+prefp[l]<Q[Q.size()-i-1].st) --l;
    kiedyq[b-i-1]=l;
  }
  for(int i=1; i<a; ++i) if(kiedyp[i]<b-1 && kiedyq[kiedyp[i]+1]<i) return false;
  for(int i=1; i<b; ++i) if(kiedyq[i]<a-1 && kiedyp[kiedyq[i]+1]<i) return false;
  return true;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k >> t;
  rep(i, n) cin >> T[i];
  rep(i, k-1) A.pb(T[i+1]-T[i]);
  for(int i=n-1; i>=k; --i) B.pb(T[i]-T[i-1]);
  reverse(all(A));
  reverse(all(B));
  ll po=0, ko=INF;
  while(po<ko) {
    ll sr=(po+ko)/2;
    if(check(sr)) ko=sr; else po=sr+1;
  }
  cout << po << '\n';
}

Compilation message (stderr)

sparklers.cpp: In function 'std::vector<std::pair<long long int, long long int> > calc(std::vector<std::pair<long long int, long long int> >)':
sparklers.cpp:15:6: warning: unused variable 'm' [-Wunused-variable]
   15 |   ll m=T.size()-1;
      |      ^
sparklers.cpp: In function 'bool check(ll)':
sparklers.cpp:36:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while(l1<P.size() && l2<Q.size()) {
      |         ~~^~~~~~~~~
sparklers.cpp:36:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while(l1<P.size() && l2<Q.size()) {
      |                        ~~^~~~~~~~~
sparklers.cpp:46:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if(l1<P.size() && P[l1].st>akt && P[l1].nd>0) return false;
      |      ~~^~~~~~~~~
sparklers.cpp:47:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   if(l2<Q.size() && Q[l2].st>akt && Q[l2].nd>0) return false;
      |      ~~^~~~~~~~~
sparklers.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=l1; i<P.size(); ++i) prefp.pb(prefp.back()+P[i].nd);
      |                 ~^~~~~~~~~
sparklers.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i=l2; i<Q.size(); ++i) prefq.pb(prefq.back()+Q[i].nd);
      |                 ~^~~~~~~~~

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