Submission #999279

#	Time	Username	Problem	Language	Result	Execution time	Memory
999279		AdamGS	Sparklers (JOI17_sparklers)	C++17	0 / 100	2066 ms	468 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<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]), T[i]};
    while(P.size()>0 && x.nd<0) {
      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<ll>X, Y;
  for(auto i : A) X.pb(2*x*t-i);
  for(auto i : B) Y.pb(2*x*t-i);
  vector<pair<ll,ll>>P=calc(X), Q=calc(Y);
  ll l1=0, l2=0, akt=0;
  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;
    }
  }
  while(l1<P.size()) {
    if(P[l1].st>akt) return false;
    akt+=P[l1].nd;
    ++l1;
  }
  while(l2<Q.size()) {
    if(Q[l2].st>akt) return false;
    akt+=Q[l2].nd;
    ++l2;
  }
  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<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:35: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]
   35 |   while(l1<P.size() && l2<Q.size()) {
      |         ~~^~~~~~~~~
sparklers.cpp:35: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]
   35 |   while(l1<P.size() && l2<Q.size()) {
      |                        ~~^~~~~~~~~
sparklers.cpp:45: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]
   45 |   while(l1<P.size()) {
      |         ~~^~~~~~~~~
sparklers.cpp:50: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]
   50 |   while(l2<Q.size()) {
      |         ~~^~~~~~~~~

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