oj.uz

Submission #1061470

# Submission time Handle Problem Language Result Execution time Memory
1061470 2024-08-16T09:34:02 Z prvocislo Peru (RMI20_peru) C++17
49 / 100
 600 ms 211888 KB 
// Your arson's match, your somber eyes
// And I'll still see it until I die
// You're the loss of my life

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int mod = 1e9 + 7, base = 23;
void upd(int& a, int b) { a = (a + b) % mod; }
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }

const int maxn = 1 << 22;
ll st[maxn * 2], lz[maxn * 2];
int l[maxn * 2], r[maxn * 2];
void update(int li, int ri, ll x, int vr = 1)
{
    if (ri < l[vr] || r[vr] < li) return;
    if (li <= l[vr] && r[vr] <= ri) return st[vr] += x, lz[vr] += x, void();
    update(li, ri, x, vr << 1), update(li, ri, x, (vr << 1) | 1);
    st[vr] = min(st[vr * 2], st[vr * 2 + 1]) + lz[vr];
}
ll query(int li, int ri, int vr = 1)
{
    if (ri < l[vr] || r[vr] < li) return 1e18;
    if (li <= l[vr] && r[vr] <= ri) return st[vr];
    return min(query(li, ri, (vr << 1)), query(li, ri, (vr << 1) | 1)) + lz[vr];
}
ll dp[maxn], s[maxn];
vector<int> mq;
int solve(int n, int k, int* S)
{
    for (int i = maxn; i < maxn * 2; i++) l[i] = r[i] = i - maxn;
    for (int i = maxn - 1; i > 0; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1];
    for (int i = 0; i < n; i++) s[i] = S[i];
    mq.push_back(-1);
    for (int i = 1; i <= n; i++) // ideme postavit prefix dlzky i
    {
        while (mq.size() > 1 && s[mq.back()] < s[i - 1]) update(mq[mq.size() - 2] + 1, mq.back(), s[i - 1] - s[mq.back()]), mq.pop_back();
        update(i - 1, i - 1, dp[i - 1] + s[i - 1]);
        mq.push_back(i - 1);
        dp[i] = query(max(0, i - k), i - 1);
        //cout << i << " : " << dp[i] << "\n";
    }
    int ans = 0, m = 1;
    for (int i = n; i >= 1; i--) upd(ans, mul(dp[i] % (ll)mod, m)), m = mul(m, base);
    return ans;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 84580 KB Output is correct
2 Correct 14 ms 84568 KB Output is correct
3 Correct 14 ms 84572 KB Output is correct
4 Correct 14 ms 84516 KB Output is correct
5 Correct 16 ms 84568 KB Output is correct
6 Correct 14 ms 84488 KB Output is correct
7 Correct 14 ms 84572 KB Output is correct
8 Correct 16 ms 84568 KB Output is correct
9 Correct 15 ms 84572 KB Output is correct
10 Correct 16 ms 84568 KB Output is correct
11 Correct 16 ms 84572 KB Output is correct
12 Correct 14 ms 84548 KB Output is correct
13 Correct 14 ms 84572 KB Output is correct
14 Correct 14 ms 84572 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 84580 KB Output is correct
2 Correct 14 ms 84568 KB Output is correct
3 Correct 14 ms 84572 KB Output is correct
4 Correct 14 ms 84516 KB Output is correct
5 Correct 16 ms 84568 KB Output is correct
6 Correct 14 ms 84488 KB Output is correct
7 Correct 14 ms 84572 KB Output is correct
8 Correct 16 ms 84568 KB Output is correct
9 Correct 15 ms 84572 KB Output is correct
10 Correct 16 ms 84568 KB Output is correct
11 Correct 16 ms 84572 KB Output is correct
12 Correct 14 ms 84548 KB Output is correct
13 Correct 14 ms 84572 KB Output is correct
14 Correct 14 ms 84572 KB Output is correct
15 Correct 230 ms 116820 KB Output is correct
16 Correct 239 ms 116928 KB Output is correct
17 Correct 218 ms 116800 KB Output is correct
18 Correct 235 ms 116804 KB Output is correct
19 Correct 234 ms 116816 KB Output is correct
20 Correct 233 ms 116672 KB Output is correct
21 Correct 219 ms 116860 KB Output is correct
22 Correct 226 ms 116336 KB Output is correct
23 Correct 239 ms 116244 KB Output is correct
24 Correct 223 ms 116076 KB Output is correct
25 Correct 220 ms 116176 KB Output is correct
26 Correct 223 ms 116776 KB Output is correct
27 Correct 220 ms 116820 KB Output is correct
28 Correct 234 ms 116820 KB Output is correct
29 Correct 254 ms 116828 KB Output is correct
30 Correct 223 ms 116840 KB Output is correct
31 Correct 215 ms 116820 KB Output is correct
32 Correct 221 ms 116820 KB Output is correct
33 Correct 218 ms 116820 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 116820 KB Output is correct
2 Correct 239 ms 116928 KB Output is correct
3 Correct 218 ms 116800 KB Output is correct
4 Correct 235 ms 116804 KB Output is correct
5 Correct 234 ms 116816 KB Output is correct
6 Correct 233 ms 116672 KB Output is correct
7 Correct 219 ms 116860 KB Output is correct
8 Correct 226 ms 116336 KB Output is correct
9 Correct 239 ms 116244 KB Output is correct
10 Correct 223 ms 116076 KB Output is correct
11 Correct 220 ms 116176 KB Output is correct
12 Correct 223 ms 116776 KB Output is correct
13 Correct 220 ms 116820 KB Output is correct
14 Correct 234 ms 116820 KB Output is correct
15 Correct 254 ms 116828 KB Output is correct
16 Correct 223 ms 116840 KB Output is correct
17 Correct 215 ms 116820 KB Output is correct
18 Correct 221 ms 116820 KB Output is correct
19 Correct 218 ms 116820 KB Output is correct
20 Correct 16 ms 84580 KB Output is correct
21 Correct 14 ms 84568 KB Output is correct
22 Correct 14 ms 84572 KB Output is correct
23 Correct 14 ms 84516 KB Output is correct
24 Correct 16 ms 84568 KB Output is correct
25 Correct 14 ms 84488 KB Output is correct
26 Correct 14 ms 84572 KB Output is correct
27 Correct 16 ms 84568 KB Output is correct
28 Correct 15 ms 84572 KB Output is correct
29 Correct 16 ms 84568 KB Output is correct
30 Correct 16 ms 84572 KB Output is correct
31 Correct 14 ms 84548 KB Output is correct
32 Correct 14 ms 84572 KB Output is correct
33 Correct 14 ms 84572 KB Output is correct
34 Execution timed out 1094 ms 211888 KB Time limit exceeded
35 Halted 0 ms 0 KB -