Submission #502183

# Submission time Handle Problem Language Result Execution time Memory
502183 2022-01-05T12:36:04 Z keta_tsimakuridze Peru (RMI20_peru) C++14
0 / 100
1 ms 340 KB
#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 = 2000 + 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;ll ans = 0, mn = 0;
  /* p[0] = 1;
    for(int i = 1; i < n; i++) p[i] = p[i - 1] * 23 % mod;
    
    
    for(int i = 1; i <= n; i++) {
    mn = max(mn, (ll)v[i - 1]); 
    	int l = i;
    	while(st.size() && st.top().f <= v[i - 1]) {
    		l = st.top().s.f;
    		upd(1, st.top().s.f, st.top().s.s, 1, n, - st.top().f + v[i - 1]);
    		st.pop();
		}
		upd(1, i, i, 1, n, dp[i - 1] + v[i - 1]);
		dp[i] = get(1, max(1, i - k + 1), i - 1, 1, n);
		if(i - k + 1 <= 0) dp[i] = min(dp[i], mn);
		st.push({v[i - 1], {l, i}});
		ans += p[n- i] * (dp[i] % mod); ans %= mod;
	}*/
	return ans;
}/*
static int s[N];
int main(){
    cin>> n >> k;
    for(int i = 0; i < n; i++){
        cin>> s[i];
    }
    int ans = solve(n, k, s);
    cout<< ans <<"\n";
    return 0;
}*/

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:40:42: warning: unused variable 'mn' [-Wunused-variable]
   40 |    stack<pair<int, pii> > st;ll ans = 0, mn = 0;
      |                                          ^~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -