oj.uz

Submission #541040

# Submission time Handle Problem Language Result Execution time Memory
541040 2022-03-22T06:56:21 Z LittleCube Fire (JOI20_ho_t5) C++14
7 / 100
 292 ms 14244 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;
    }
    sort(q + 1, q + 1 + Q, [](query q1, query q2)
         { return q1.L < q2.L; });
    int qdx = 1;
    vector<pll> v;
    for (int i = 1; i <= N; i++)
    {
        while(!v.empty() && v.back().S <= arr[i])
            v.pop_back();
        v.push_back(pll{i, arr[i]});
        while (qdx <= Q && q[qdx].L == i)
        {
            ans[q[qdx].i] = lower_bound(v.begin(), v.end(), pll{i - q[qdx].T, 0})->S;
            qdx++;
        }
        
    }
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << '\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
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 281 ms 8576 KB Output is correct
3 Correct 271 ms 13796 KB Output is correct
4 Correct 292 ms 14156 KB Output is correct
5 Correct 274 ms 13608 KB Output is correct
6 Correct 292 ms 13836 KB Output is correct
7 Correct 279 ms 13856 KB Output is correct
8 Correct 273 ms 14128 KB Output is correct
9 Correct 270 ms 13840 KB Output is correct
10 Correct 264 ms 13644 KB Output is correct
11 Correct 271 ms 14244 KB Output is correct
12 Correct 263 ms 13768 KB Output is correct
13 Correct 279 ms 14184 KB Output is correct
14 Correct 257 ms 13860 KB Output is correct
15 Correct 272 ms 14084 KB Output is correct
16 Correct 261 ms 13612 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 6760 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 -