This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 + 100;
#define int long long
vector<int> w, mst[4*MAXN];
int ans[4*MAXN];
void merge(int k) {
vector<int> A = mst[2*k];
vector<int> B = mst[2*k+1];
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
int mx_B = -2e9;
while (A.size() || B.size()) {
int valA = (A.size() ? A.back() : 2e9);
int valB = (B.size() ? B.back() : 2e9);
if (valA <= valB) {
mst[k].push_back(valA);
ans[k] = max(ans[k], valA + mx_B);
A.pop_back();
} else {
mst[k].push_back(valB);
mx_B = max(mx_B, valB);
B.pop_back();
}
}
}
void init(int k, int a, int b) {
if (a == b) {
ans[k] = 0;
mst[k].push_back(w[a]);
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
merge(k);
}
pair<int,int> query(int k, int a, int b, int q_l, int q_r, int mx) {
if (b < q_l || a > q_r)
return {-2e9, -2e9};
if (q_l <= a && b <= q_r) {
auto lb = lower_bound(mst[k].begin(), mst[k].end(), mx);
if (lb == mst[k].begin() || mst[k].size() == 0)
return {max(mx, mst[k].back()), ans[k]};
return {max(mx, mst[k].back()), max(ans[k], mx + *prev(lb))};
}
pair<int,int> Q1 = query(2*k, a, (a+b)/2, q_l, q_r, mx);
pair<int,int> Q2 = query(2*k+1, (a+b)/2+1, b, q_l, q_r, max(mx, Q1.f));
pair<int,int> new_p = {max(Q1.f, Q2.f), max(Q1.s, Q2.s)};
return new_p;
}
signed main() {
fast
int N, M;
cin >> N >> M;
w = vector<int>(N+1);
for (int i = 1; i <= N; i++)
cin >> w[i];
init(1, 1, N);
for (int i = 0; i < M; i++) {
int l, r, k;
cin >> l >> r >> k;
int Q = query(1, 1, N, l, r, -2e9).s;
if (Q > k)
cout << "0\n";
else
cout << "1\n";
}
}
# | 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... |