// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
template<class T> using V = vector<T>;
const int INF = 1e9+10;
struct BIT {
int N; V<int> A; void init(int n) { N = n; A = V<int>(N, INF); }
void upd(int p, int x) { p = N - 1 - p; for(++p;p<=N;p+=p&-p) A[p-1] = min(A[p-1], x);}
int get(int r) { r = N - 1 - r; int s = INF; for(++r;r;r-=r&-r) s = min(A[r-1], s); return s; }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, K; cin >> N >> K;
V<int> A(N); for(auto& x : A) cin >> x;
BIT B; B.init(N);
V<array<int, 4>> Q(K); for(int i = 0; i < K; i++) {
cin >> Q[i][1] >> Q[i][2] >> Q[i][0];
--Q[i][1], --Q[i][2];
Q[i][3] = i;
}
V<array<int, 3>> E;
V<pair<int, int>> stk = {{-1, -1}};
for(int i = N - 1; i >= 0; i--) {
int pos = i;
while(stk.back().first != -1 && A[stk.back().first] <= A[i]) {
int x = A[stk.back().first] + A[i];
// cout << x << " " << i << " " << pos << endl;
E.push_back({x, i, pos});
pos = max(pos, stk.back().second);
stk.pop_back();
}
B.upd(i, N);
stk.push_back({i, pos});
}
sort(rbegin(Q), rend(Q));
sort(rbegin(E), rend(E));
vector<int> ans(K);
int j = 0;
for(int q = 0; q < K; q++) {
// cout << q << endl;
while(j < int(size(E)) && E[j][0] > Q[q][0]) {
auto [k, i, x] = E[j];
// cout << i << " " << x << endl;
B.upd(i, x);
j++;
}
auto [k, l, r, i] = Q[q];
int x = B.get(l);
// cout << l << " " << r << " " << x << endl;
ans[i] = x >= r;
}
for(auto x : ans) cout << x << nl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
629 ms |
73344 KB |
Output is correct |
| 2 |
Correct |
626 ms |
74344 KB |
Output is correct |
| 3 |
Correct |
653 ms |
74236 KB |
Output is correct |
| 4 |
Correct |
676 ms |
74376 KB |
Output is correct |
| 5 |
Incorrect |
480 ms |
70628 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
6352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
