Submission #640174

#	Time	Username	Problem	Language	Result	Execution time	Memory
640174		danikoynov	Peru (RMI20_peru)	C++14	49 / 100	1099 ms	106824 KiB

peru

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2.5e6 + 10;
const ll inf = 1e18, mod = 1e9 + 7;

ll a[maxn], dp[maxn], tree[4 * maxn], lazy[4 * maxn];

void push_lazy(int root, int left, int right)
{
    tree[root] += lazy[root];

    if (left != right)
    {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
    }

    lazy[root] = 0;
}
void update(int root, int left, int right, int pos, ll val)
{
    push_lazy(root, left, right);

    if (left == right)
    {
        tree[root] = val;
        return;
    }

    int mid = (left + right) / 2;
    if (pos <= mid)
        update(root * 2, left, mid, pos, val);
    else
        update(root * 2 + 1, mid + 1, right, pos, val);

    tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}

ll query(int root, int left, int right, int qleft, int qright)
{
    push_lazy(root, left, right);

    if (left > qright || right < qleft)
        return inf;

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return min(query(root * 2, left, mid, qleft, qright),
               query(root * 2 + 1, mid + 1, right, qleft, qright));

}

void range_update(int root, int left, int right, int qleft, int qright, ll val)
{
    ///cout << root << " " << left << " " << right << endl;
    push_lazy(root, left, right);

    if (left > qright || right < qleft)
        return;
    if (left >= qleft && right <= qright)
    {
        lazy[root] += val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    range_update(root * 2, left, mid, qleft, qright, val);
    range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}

int solve(int n, int k, int *S)
{
    for (int i = 0; i < n; i ++)
        a[i + 1] = S[i];


    update(1, 0, n, 0, a[1]);
    stack < int > st;
    st.push(1);
    for (int i = 1; i <= n; i ++)
    {
        ///cout << "---------------- " << i << endl;
        dp[i] = query(1, 0, n, max(0, i - k), i - 1);
        update(1, 0, n, i, dp[i] + a[i + 1]);
        if (i != n)
        {
            while(!st.empty() && a[st.top()] < a[i + 1])
            {
                int pos = st.top();
                st.pop();
                int from = 1;
                if (!st.empty())
                    from = st.top() + 1;
                ///cout << from << " " << pos << endl;
                range_update(1, 0, n, from - 1, pos - 1, a[i + 1] - a[pos]);
                ///cout << "finito" << endl;
            }
        }
        st.push(i + 1);
        /**ll mx = a[i];
        for (int j = i - 1; j >= max(0, i - k); j --)
        {
            dp[i] = min(dp[i], dp[j] + mx);
            mx = max(mx, a[j]);
        }*/

    }

    /**for (int i = 1; i <= n; i ++)
        cout << dp[i] << " ";
    cout << endl;*/
    ll cur = 1, ans = 0;
    for (int i = n; i > 0; i --)
    {
        ans = (ans + (dp[i] % mod) * cur) % mod;
        cur = (cur * (ll)23) % mod;
    }
    return ans;
}

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