Submission #483752

#	Time	Username	Problem	Language	Result	Execution time	Memory
483752		Rainbowbunny	Peru (RMI20_peru)	C++17	0 / 100	1 ms	468 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e6 + 5e5 + 5;
const int mod = 1e9 + 7;

int Add(int x, int y)
{
    return x + y >= mod ? x + y - mod : x + y;
}

int Mul(int x, int y)
{
    return 1ll * x * y % mod;
}

int L[MAXN], dp[MAXN];
int ST[22][MAXN];

int Get(int l, int r)
{
    int tmp = L[r - l + 1];
    return max(ST[tmp][l], ST[tmp][r - (1 << tmp) + 1]);
}

int solve(int n, int k, int* v)
{
    L[0] = -1;
    for(int i = 0; i < n; i++)
    {
        ST[0][i + 1] = v[i];
        L[i + 1] = L[(i + 1) >> 1] + 1; 
    }
    for(int i = 1; i < 22; i++)
    {
        for(int j = 1; j + (1 << i) <= n + 1; j++)
        {
            ST[i][j] = max(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
        }
    }
    deque <int> Q;
    Q.push_back(0);
    for(int i = 1; i <= n; i++)
    {
        while(!Q.empty() and Q.front() <= i - k - 1)
        {
            Q.pop_front();
        }
        while(Q.size() >= 2)
        {
            int tmp1 = Q.front();
            Q.pop_front();
            int tmp2 = Q.front();
            if(dp[tmp1] + Get(tmp1 + 1, i) <= dp[tmp2] + Get(tmp2 + 1, i))
            {
                Q.push_front(tmp1);
                break;
            }
        }
        dp[i] = dp[Q.front()] + Get(Q.front() + 1, i);
        while(!Q.empty() and dp[Q.back()] + Get(Q.back() + 1, i + 1) > dp[i] + v[i])
        {
            Q.pop_back();
        }
        Q.push_back(i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans = Mul(ans, 23);
        ans = Add(ans, dp[i]);
    }
    return ans;
}

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