Submission #1061470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061470		prvocislo	Peru (RMI20_peru)	C++17	49 / 100	1094 ms	211888 KiB

peru

// Your arson's match, your somber eyes
// And I'll still see it until I die
// You're the loss of my life

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int mod = 1e9 + 7, base = 23;
void upd(int& a, int b) { a = (a + b) % mod; }
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }

const int maxn = 1 << 22;
ll st[maxn * 2], lz[maxn * 2];
int l[maxn * 2], r[maxn * 2];
void update(int li, int ri, ll x, int vr = 1)
{
    if (ri < l[vr] || r[vr] < li) return;
    if (li <= l[vr] && r[vr] <= ri) return st[vr] += x, lz[vr] += x, void();
    update(li, ri, x, vr << 1), update(li, ri, x, (vr << 1) | 1);
    st[vr] = min(st[vr * 2], st[vr * 2 + 1]) + lz[vr];
}
ll query(int li, int ri, int vr = 1)
{
    if (ri < l[vr] || r[vr] < li) return 1e18;
    if (li <= l[vr] && r[vr] <= ri) return st[vr];
    return min(query(li, ri, (vr << 1)), query(li, ri, (vr << 1) | 1)) + lz[vr];
}
ll dp[maxn], s[maxn];
vector<int> mq;
int solve(int n, int k, int* S)
{
    for (int i = maxn; i < maxn * 2; i++) l[i] = r[i] = i - maxn;
    for (int i = maxn - 1; i > 0; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1];
    for (int i = 0; i < n; i++) s[i] = S[i];
    mq.push_back(-1);
    for (int i = 1; i <= n; i++) // ideme postavit prefix dlzky i
    {
        while (mq.size() > 1 && s[mq.back()] < s[i - 1]) update(mq[mq.size() - 2] + 1, mq.back(), s[i - 1] - s[mq.back()]), mq.pop_back();
        update(i - 1, i - 1, dp[i - 1] + s[i - 1]);
        mq.push_back(i - 1);
        dp[i] = query(max(0, i - k), i - 1);
        //cout << i << " : " << dp[i] << "\n";
    }
    int ans = 0, m = 1;
    for (int i = n; i >= 1; i--) upd(ans, mul(dp[i] % (ll)mod, m)), m = mul(m, base);
    return ans;
}

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