oj.uz

Submission #656818

# Submission time Handle Problem Language Result Execution time Memory
656818 2022-11-08T08:58:40 Z lovrot Peru (RMI20_peru) C++17
0 / 100
 1 ms 340 KB 
#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, int *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();
	}
	
	//for(int i = 0; i < n; i++) printf("%lld ", dp[i]);
	//printf("\n");
	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;
}*/

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -