oj.uz

Submission #640174

# Submission time Handle Problem Language Result Execution time Memory
640174 2022-09-13T20:12:59 Z danikoynov Peru (RMI20_peru) C++14
49 / 100
 600 ms 106824 KB 
#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.0 / 18.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 412 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 307 ms 24784 KB Output is correct
16 Correct 305 ms 25016 KB Output is correct
17 Correct 308 ms 24856 KB Output is correct
18 Correct 344 ms 24800 KB Output is correct
19 Correct 314 ms 24752 KB Output is correct
20 Correct 323 ms 24828 KB Output is correct
21 Correct 305 ms 24860 KB Output is correct
22 Correct 319 ms 24952 KB Output is correct
23 Correct 307 ms 24864 KB Output is correct
24 Correct 303 ms 24800 KB Output is correct
25 Correct 308 ms 24928 KB Output is correct
26 Correct 317 ms 24756 KB Output is correct
27 Correct 311 ms 24936 KB Output is correct
28 Correct 310 ms 24908 KB Output is correct
29 Correct 312 ms 24844 KB Output is correct
30 Correct 303 ms 24756 KB Output is correct
31 Correct 298 ms 24812 KB Output is correct
32 Correct 322 ms 24928 KB Output is correct
33 Correct 295 ms 24780 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 24784 KB Output is correct
2 Correct 305 ms 25016 KB Output is correct
3 Correct 308 ms 24856 KB Output is correct
4 Correct 344 ms 24800 KB Output is correct
5 Correct 314 ms 24752 KB Output is correct
6 Correct 323 ms 24828 KB Output is correct
7 Correct 305 ms 24860 KB Output is correct
8 Correct 319 ms 24952 KB Output is correct
9 Correct 307 ms 24864 KB Output is correct
10 Correct 303 ms 24800 KB Output is correct
11 Correct 308 ms 24928 KB Output is correct
12 Correct 317 ms 24756 KB Output is correct
13 Correct 311 ms 24936 KB Output is correct
14 Correct 310 ms 24908 KB Output is correct
15 Correct 312 ms 24844 KB Output is correct
16 Correct 303 ms 24756 KB Output is correct
17 Correct 298 ms 24812 KB Output is correct
18 Correct 322 ms 24928 KB Output is correct
19 Correct 295 ms 24780 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 412 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Execution timed out 1099 ms 106824 KB Time limit exceeded
35 Halted 0 ms 0 KB -