Submission #900537

#	Time	Username	Problem	Language	Result	Execution time	Memory
900537		Cookie	Peru (RMI20_peru)	C++14	49 / 100	357 ms	63556 KiB

peru

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#include<iostream>
#include "peru.h"
using namespace std;
const int mxn = 4e5 + 5;
const ll mod = 1e9 + 7, inf = 1e18;
ll a[mxn + 1];
ll dp[mxn + 1], pw[mxn + 1];
ll st[4 * mxn + 1], lz[4 * mxn + 1];

void push(int nd){
    ll &v = lz[nd];
    lz[nd << 1] += v; lz[nd << 1 | 1] += v; st[nd << 1] += v; st[nd << 1 | 1] += v;
    v = 0;
}
void upd(int nd, int l, int r, int ql, int qr, ll v){
    //if(nd == 1)cout << ql << " " << qr << " " << v << "\n";
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        st[nd] += v; lz[nd] += v; return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
    st[nd] = min(st[nd << 1], st[nd << 1 | 1]);
}
ll get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(inf);
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    push(nd);
    return(min(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
int solve(int n, int k, int* v){
    pw[0] = 1;
    for(int i = 1; i < n; i++)pw[i] = (pw[i - 1] * 23) % mod;
    for(int i = 1; i <= n; i++)a[i] = v[i - 1];
    deque<pair<int, int>>dq;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        int last = i - 2;
        while(sz(dq) && dq.back().se <= a[i]){
            upd(1, 0, n, dq.back().fi - 1, last, a[i] - dq.back().se); last = dq.back().fi - 2; dq.pop_back();
        }

        dq.pb(mpp(last + 2, a[i]));
        upd(1, 0, n, i - 1, i - 1, a[i]);
       
        dp[i] = get(1, 0, n, max(i - k, 0), i - 1);
        upd(1, 0, n, i, i, dp[i]);
        
        ans = (ans + (dp[i] % mod) * pw[n - i]) % mod;
    }
    return(ans);
}

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