oj.uz

Submission #854697

# Submission time Handle Problem Language Result Execution time Memory
854697 2023-09-28T14:44:00 Z tibinyte Peru (RMI20_peru) C++17
49 / 100
 600 ms 118244 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 213 ms 20060 KB Output is correct
16 Correct 220 ms 20108 KB Output is correct
17 Correct 213 ms 20200 KB Output is correct
18 Correct 209 ms 20008 KB Output is correct
19 Correct 209 ms 20000 KB Output is correct
20 Correct 209 ms 20000 KB Output is correct
21 Correct 211 ms 20108 KB Output is correct
22 Correct 220 ms 20248 KB Output is correct
23 Correct 218 ms 20056 KB Output is correct
24 Correct 218 ms 20128 KB Output is correct
25 Correct 219 ms 20308 KB Output is correct
26 Correct 213 ms 20056 KB Output is correct
27 Correct 211 ms 20076 KB Output is correct
28 Correct 218 ms 20124 KB Output is correct
29 Correct 215 ms 20088 KB Output is correct
30 Correct 213 ms 20108 KB Output is correct
31 Correct 209 ms 20068 KB Output is correct
32 Correct 214 ms 20140 KB Output is correct
33 Correct 210 ms 20116 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 20060 KB Output is correct
2 Correct 220 ms 20108 KB Output is correct
3 Correct 213 ms 20200 KB Output is correct
4 Correct 209 ms 20008 KB Output is correct
5 Correct 209 ms 20000 KB Output is correct
6 Correct 209 ms 20000 KB Output is correct
7 Correct 211 ms 20108 KB Output is correct
8 Correct 220 ms 20248 KB Output is correct
9 Correct 218 ms 20056 KB Output is correct
10 Correct 218 ms 20128 KB Output is correct
11 Correct 219 ms 20308 KB Output is correct
12 Correct 213 ms 20056 KB Output is correct
13 Correct 211 ms 20076 KB Output is correct
14 Correct 218 ms 20124 KB Output is correct
15 Correct 215 ms 20088 KB Output is correct
16 Correct 213 ms 20108 KB Output is correct
17 Correct 209 ms 20068 KB Output is correct
18 Correct 214 ms 20140 KB Output is correct
19 Correct 210 ms 20116 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Execution timed out 1028 ms 118244 KB Time limit exceeded
35 Halted 0 ms 0 KB -