Submission #854697

#	Time	Username	Problem	Language	Result	Execution time	Memory
854697		tibinyte	Peru (RMI20_peru)	C++17	49 / 100	1028 ms	118244 KiB

peru

#include <bits/stdc++.h>
#include "peru.h"


using namespace std;

typedef long long ll;

const ll inf = 1e16;

const int mod = 1e9 + 7;

struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint operator*(Mint oth)
    {
        return 1ll * val * oth.val;
    }
};

Mint powmod(int a, int b)
{
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 1)
    {
        return powmod(a, b - 1) * a;
    }
    Mint P = powmod(a, b / 2);
    return P * P;
}

struct aint
{
    vector<ll> a;
    void resize(int n)
    {
        a = vector<ll>(4 * n, inf);
    }
    void update(int node, int left, int right, int pos, ll val)
    {
        if (left == right)
        {
            a[node] = val;
            return;
        }
        int mid = (left + right) / 2;
        if (pos <= mid)
        {
            update(2 * node, left, mid, pos, val);
        }
        else
        {
            update(2 * node + 1, mid + 1, right, pos, val);
        }
        a[node] = min(a[2 * node], a[2 * node + 1]);
    }
    ll query(int node, int left, int right, int st, int dr)
    {
        if (right < st || left > dr)
        {
            return inf;
        }
        if (st <= left && dr >= right)
        {
            return a[node];
        }
        int mid = (left + right) / 2;
        return min(query(2 * node, left, mid, st, dr), query(2 * node + 1, mid + 1, right, st, dr));
    }
};

int solve(int n, int k, int *S)
{
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        a[i] = S[i - 1];
    }
    Mint ans = 0;
    vector<ll> dp(n + 1, inf);
    vector<int> s;
    aint tree;
    tree.resize(n);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        while (!s.empty() && a[s.back()] < a[i])
        {
            tree.update(1, 1, n, s.back(), inf);
            s.pop_back();
        }
        if (s.empty())
        {
            tree.update(1, 1, n, i, a[i]);
        }
        else
        {
            tree.update(1, 1, n, i, a[i] + dp[s.back()]);
        }
        s.push_back(i);
        int st = 0, dr = (int)s.size() - 1;
        int rep = -1;
        while (st <= dr)
        {
            int mid = (st + dr) / 2;
            if (s[mid] >= i - k + 1)
            {
                rep = s[mid];
                dr = mid - 1;
            }
            else
            {
                st = mid + 1;
            }
        }
        assert(rep != -1);
        if (rep + 1 <= i)
        {
            dp[i] = tree.query(1, 1, n, rep + 1, i);
        }
        dp[i] = min(dp[i], a[rep] + dp[max(0, i - k)]);
        ans = ans + powmod(23, n - i) * dp[i];
    }
    return ans.val;
}

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