Submission #656835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
656835	2022-11-08T09:29:20 Z	lovrot	Peru (RMI20_peru)	C++17	Compilation error	0 ms	0 KB

peru

#include "peru.h"
#include <bits/stdc++.h> 
 
#define X first
#define Y second
#define ll long long
#define pii pair<ll, ll>

using namespace std; 

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int N = 2500010;

ll dp[N];
ll d[2 * N + 10];
int l_ind = N, r_ind = N + 1;

stack<pii> hist;
stack<pii> l, r;

ll add(ll a, ll b){
	if(a + b < MOD) return a + b;
	return a + b - MOD;
}

ll mult(ll a, ll b){
	return (ll) a * b % MOD;
}

ll eval(int n){
	ll res = 0;
	ll prod = 1;
	
	for(int i = n - 1; i >= 0; i--){
		res = add(res, mult(dp[i], prod));
		prod = mult(prod, 23);
	}	
	return res;
}
//////////////////////////////////////////////////
int histogram(int x, ll val){
	int ret = 0;
	while(!hist.empty() && hist.top().X < val){
		hist.pop();
	}
	if(!hist.empty()) ret = hist.top().Y + 1;
	hist.push({val, x});
	return ret;
}

void pop(stack<pii> &p){ //stack
	if(!p.empty()) p.pop();
}

void push(stack<pii> &p, ll val){ //stack
	if(p.empty()) p.push({val, val});
	else p.push({val, min(val, p.top().Y)});
}

void build(){ //deck
	if(!l.empty() && !r.empty()) return;
	while(!l.empty()) pop(l);
	while(!r.empty()) pop(r);
	int mi = (l_ind + r_ind) / 2;
	for(int i = mi; i > l_ind; i--) push(l, d[i]);		
	for(int i = mi + 1; i < r_ind; i++) push(r, d[i]);
}

void pop_left(){
	l_ind++;
	pop(l);
	build();
}

void pop_right(){
	r_ind--;
	pop(r);
	build();
}

void push_right(ll val){
	d[r_ind] = val;
	r_ind++;
	push(r, val);
}

ll getMin(){
	ll ret = INF;
	if(!l.empty()) ret = min(ret, l.top().Y);
	if(!r.empty()) ret = min(ret, r.top().Y);
	return ret;
}

int solve(int n, int k, ll *s){
	dp[0] = s[0];	
	push_right(dp[0]);
	histogram(0, s[0]);
	for(int i = 1; i < n; i++){
		if(i >= k) pop_left();
		int pos = max(histogram(i, s[i]), i - k + 1);
		//printf("%d: %d\n", i, pos);
		for(int j = pos; j < i; j++) pop_right();
		for(int j = pos; j <= i; j++){ 
			if(j > 0) push_right(dp[j - 1] + s[i]);
			else push_right(s[i]);
		}
		dp[i] = getMin();
	}
	
	return eval(n);
}
/*
int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	int arr[n];
	for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
	printf("%d\n", solve(n, k, arr));
	return 0;
}*/

Compilation message

/usr/bin/ld: /tmp/ccptBBcv.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status