oj.uz

Submission #541039

# Submission time Handle Problem Language Result Execution time Memory
541039 2022-03-22T06:50:17 Z LittleCube Fire (JOI20_ho_t5) C++14
6 / 100
 267 ms 13732 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

struct query
{
    int i, T, L, R;
};

ll N, Q, arr[200005], ans[200005];
query q[200005];

signed main()
{
    cin >> N >> Q;
    for (int i = 1; i <= N; i++)
        cin >> arr[i];

    for (int i = 1; i <= Q; i++)
    {
        cin >> q[i].T >> q[i].L >> q[i].R;
        q[i].i = i;
    }

    int T = q[1].T;
    deque<pll> dq;
    for (int i = 1; i <= N; i++)
    {
        if (!dq.empty() && dq.back().S < i - T)
            dq.pop_back();
        while (!dq.empty() && dq.front().F < arr[i])
            dq.pop_front();
        dq.push_front(pll{arr[i], i});
        arr[i] = dq.back().F;
    }
    for (int i = 1; i <= N; i++)
        arr[i] += arr[i - 1];
    for (int i = 1; i <= Q; i++)
    {
        cout << arr[q[i].R] - arr[q[i].L - 1] << '\n';
    }
}

Subtask #1
0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 259 ms 7632 KB Output is correct
3 Correct 251 ms 7628 KB Output is correct
4 Correct 257 ms 7992 KB Output is correct
5 Correct 260 ms 13368 KB Output is correct
6 Correct 256 ms 13228 KB Output is correct
7 Correct 252 ms 13504 KB Output is correct
8 Correct 264 ms 13372 KB Output is correct
9 Correct 252 ms 13488 KB Output is correct
10 Correct 267 ms 13380 KB Output is correct
11 Correct 262 ms 13732 KB Output is correct
12 Correct 253 ms 13316 KB Output is correct
13 Correct 255 ms 13204 KB Output is correct
14 Correct 243 ms 13180 KB Output is correct
15 Correct 244 ms 13276 KB Output is correct
16 Correct 257 ms 13160 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 259 ms 6872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

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