Submission #401605

#	Time	Username	Problem	Language	Result	Execution time	Memory
401605		maximath_1	Peru (RMI20_peru)	C++17	100 / 100	158 ms	60156 KiB

peru

#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
 
#define ll long long
const ll mod = 1e9 + 7;
const ll base = 23;
const ll inf_ll = mod * 2ll * mod + 69ll;
const int MX = 2500005;
 
ll pwbase[MX];
int n, k, v[MX];
ll dp[MX];
struct dt{
	int id;
	ll dp_id, dp_min;
};
deque<dt> dq;
 
int vv = 0;
void pop_front(){
	if(dq.size()) dq.pop_front();
	if(dq.size()){
		ll dp_i = dq.front().dp_id;
		dq.front().dp_id = inf_ll;
		dq.front().dp_min = inf_ll;
 
		for(int i = 1; i < dq.size(); i ++){
			if(dq[i].dp_id <= dp_i) break;
			vv ++;
			dq[i].dp_min = min(dq[i - 1].dp_min, dq[i].dp_id);
		}
	}
}
 
void push_back(int id){
	if(dq.empty()){
		dq.push_back((dt){id, inf_ll, inf_ll});
		return;
	}
 
	ll bf = dp[dq.back().id];
	dq.push_back((dt){id, bf + v[id], min(bf + v[id], dq.back().dp_min)});
	return;
}
 
int solve(int N, int K, int* V){
	n = N; k = K;
	for(int i = 0; i < n; i ++) v[i] = V[i];
 
	for(int i = 0; i < n; i ++){
		if(dq.size() && i - dq.front().id >= k) pop_front();
		while(dq.size() && v[i] >= v[dq.back().id]) dq.pop_back();
 
		push_back(i);
		dp[i] = (ll)v[dq.front().id];
 
		if(i >= k) dp[i] += dp[i - k];
		if(dq.size())
			dp[i] = min(dp[i], dq.back().dp_min);
	}
 
	assert(vv <= 5 * n);
 
	pwbase[0] = 1ll;
	for(int i = 1; i < n; i ++)
		pwbase[i] = (pwbase[i - 1] * 1ll * base) % mod;
 
	ll ans = 0ll;
 
	for(int i = 0; i < n; i ++){
		dp[i] %= mod;
		(ans += (pwbase[n - 1 - i] * 1ll * dp[i]) % mod) %= mod;
	}
 
	return ans;
}

Compilation message (stderr)

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

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