oj.uz

Submission #541036

# Submission time Handle Problem Language Result Execution time Memory
541036 2022-03-22T06:47:08 Z LittleCube Fire (JOI20_ho_t5) C++14
0 / 100
 271 ms 13540 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().F <= 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 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 268 ms 13368 KB Output is correct
3 Correct 254 ms 13372 KB Output is correct
4 Incorrect 271 ms 13540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

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