이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int MAXN = (int)(1e6) + 5;
struct Query {
int l, i, k;
};
int arr[MAXN];
bool ans[MAXN];
vector<Query> qs[MAXN];
int seg[4*MAXN];
void upd(int i, int val, int n = 1, int tl = 0, int tr = MAXN-1) {
if (tl == tr) {
seg[i] = val;
}
else {
int tm = (tl + tr)/2;
if (i <= tm) {
upd(i, val, 2*n, tl, tm);
}
else {
upd(i, val, 2*n+1, tm+1, tr);
}
seg[n] = max(seg[2*n], seg[2*n+1]);
}
}
int query(int l, int r, int n = 1, int tl = 0, int tr = MAXN-1) {
if (l > tr || r < tl) {
return 0;
}
else if (l <= tl && tr <= r) {
return seg[n];
}
else {
int tm = (tl + tr)/2;
return max(query(l, tm, 2*n, tl, tm), query(tm+1, tr, 2*n+1, tm+1, tr));
}
}
int main() {
cin.tie(0);
cin.sync_with_stdio(0);
int N, M;
cin >> N >> M;
FR(i, N) cin >> arr[i];
deque<pair<int, int>> deq;
deq.push_back({arr[0], 0});
FR(i, M) {
int l, r, k;
cin >> l >> r >> k;
l--, r--;
qs[r].push_back({l, i, k});
}
for (int i = 0; i < N; i++) {
while (deq.size() && deq.back().first <= arr[i]) {
deq.pop_back();
}
if (deq.size()) {
upd(deq.back().second, deq.back().first+arr[i]);
}
deq.push_back({arr[i], i});
for (Query q : qs[i]) {
ans[q.i] = (query(q.l, i) <= q.k);
}
}
for (int i = 0; i < M; i++) {
cout << ans[i] << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |