Submission #502174

#	Time	Username	Problem	Language	Result	Execution time	Memory
502174		keta_tsimakuridze	Peru (RMI20_peru)	C++14	0 / 100	2 ms	468 KiB

peru

#include<bits/stdc++.h>
#include "peru.h"
#define f first
#define s second
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const int N = 4e5 + 5, mod = 1e9 + 7;
ll lazy[4 * N], tree[4 * N], k, n, p[N], dp[N];
void push(int u,int l,int r) {
	if(!lazy[u]) return;
	tree[u] += lazy[u];
	if(l != r) {
		lazy[2 * u] += lazy[u];
		lazy[2 * u + 1] += lazy[u];
	}
	lazy[u] = 0;
}
void upd(int u,int st,int en,int l,int r,int val) {
	push(u, l, r);
	if(l > en || r < st) return;
	if(st <= l && r <= en) {
		lazy[u] = val;
		push(u, l, r);
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, st, en, l, mid, val); upd(2 * u + 1, st, en, mid + 1, r, val);
	tree[u] = min(tree[2 * u], tree[2 * u + 1]);
}
ll get(int u,int st,int en, int l,int r) {
	push(u, l, r);
	if(l > en || r < st) return 1e18;
	if(st <= l && r <= en) return tree[u];
	int mid = (l + r) / 2;
	return min(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
int solve(int n, int k, int* v){
    stack<pair<int, pii> > st;
    vector<int> s(n + 5);
    p[0] = 1;
    for(int i = 1; i < n; i++) p[i] = p[i - 1] * 23 % mod;
    ll ans = 0, mn = 0;
    for(int i = 1; i <= n; i++) {
    	s[i] = v[i - 1]; mn = max(mn, (ll)s[i]);
    	int l = i;
    	while(st.size() && st.top().f <= s[i]) {
    		l = st.top().s.f;
    		upd(1, st.top().s.f, st.top().s.s, 0, n, - st.top().f + s[i]);
    		st.pop();
		}
		upd(1, i, i, 0, n, dp[i - 1] + s[i]);
		dp[i] = get(1, max(1, i - k + 1), i - 1, 0, n);
		if(i - k + 1 <= 0) dp[i] = min(dp[i], mn);
		st.push({s[i], {l, i}});
		ans += p[n- i] * (dp[i] % mod); ans %= mod;

	}
	return ans;
}

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