oj.uz

Submission #483752

# Submission time Handle Problem Language Result Execution time Memory
483752 2021-11-01T03:06:11 Z Rainbowbunny Peru (RMI20_peru) C++17
0 / 100
 1 ms 468 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -