Submission #398518

#	Time	Username	Problem	Language	Result	Execution time	Memory
398518		model_code	Peru (RMI20_peru)	C++17	100 / 100	157 ms	57724 KiB

peru

/**
* user:  ivan-df9
* fname: Tudor
* lname: Ivan
* task:  Peru
* score: 100.0
* date:  2020-12-03 13:09:25.222712
*/
#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2500005;
long long dp[N];
const long long MOD = 1e9 + 7;
struct dqueelem{
  int i;
  long long dpi;
  long long dmin;
};
deque<dqueelem> dq;

bool indeq[N];

/*inline void addmn(int i, int val){
  if(indeq[i] == true)
    return;
  while(mndq.size() && (indeq[mndq.back().i] == false)){
    mndq.pop_back();
  }
  if(mndq.size() == 0 || mndq.back().dpi > val)
    mndq.push_back({i, val}), indeq[i] =true;

}*/
inline void ppbk(){
  indeq[dq.back().i] = 0;
  dq.pop_back();
}

inline void addbk(int i, int* v){
  if(dq.size() == 0){
    dq.push_back({i, LLONG_MAX, LLONG_MAX});
    return;
  }
  long long dpfr = dp[dq.back().i];
  dqueelem x({i, dpfr + v[i], min(dpfr + v[i], dq.back().dmin)});
  dq.push_back(x);
}
inline void ppfrt(){

  if(dq.size()){
    indeq[dq.front().i] = false;
    dq.pop_front();
  }
  if(dq.size()){
    long long dqf = dq.front().dpi;
    dq.front().dpi = LLONG_MAX;
    dq.front().dmin = LLONG_MAX;
    for(int i=1;i<dq.size();i++){
      if(dq[i].dpi <= dqf)
        break;
      dq[i].dmin = min(dq[i].dpi, dq[i-1].dmin);
    }
    indeq[dq.front().i] = false;
  }
}
int solve(int n, int k, int* v){
  for(int i = 0; i< n ; i++){
    if(dq.size() && i - dq.front().i >= k)
      ppfrt();
    //dbg();
    while(dq.size() && v[i] >= v[dq.back().i])
      ppbk();
    //dbg();
    addbk(i, v);
   // dbg();
    dp[i] = 1LL * v[dq.front().i];
   // for(auto x:dq){
  //    cout<<x.i<<" "<<x.dpi<<" "<<x.dmin<<"\n";
 //   }
  //  cout<<"ok\n";
    if(i - k >= 0 )
      dp[i] += dp[i - k];
   // dbg();
    if(dq.size()){
      dp[i] = min(dp[i], dq.back().dmin);
    }
  }
  long long ans = 0;
  for(int i = 0; i < n; i++){
    ans*=23LL;
    ans%=MOD;
    dp[i]%=MOD;
    ans+=dp[i];
    ans%=MOD;
  }
  dq.clear();
  return ans;
}

Compilation message (stderr)

peru.cpp: In function 'void ppfrt()':
peru.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<dqueelem>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=1;i<dq.size();i++){
      |                 ~^~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 31 / 31
• Subtask 3: 51 / 51