#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#define PB push_back
#define deb(...) //fprintf(stderr, __VA_ARGS__)
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
int n, w[N], l[N], k[N];
int prf[N], suf[N];
vector<pii> q[N], mxq[N];
set<int> s;
bool ans[N];
void dnc(int lo, int hi) {
if(lo + 1 >= hi) { return; }
int mi = (lo + hi) / 2;
dnc(lo, mi);
dnc(mi, hi);
deb("%d %d %d:\n", lo, mi, hi);
prf[mi] = 0;
suf[mi - 1] = 0;
for(int i = mi - 1, mx = 0; i >= lo; --i) {
mx = max(mx, w[i]);
prf[i] = prf[i + 1];
auto it = s.lower_bound(w[i]);
if(it != s.begin()) { prf[i] = max(prf[i], w[i] + *prev(it)); }
s.insert(w[i]);
for(; !q[i].empty() && q[i].back().X >= mi; q[i].pop_back()) {
mxq[q[i].back().X].PB({mx, q[i].back().Y});
}
}
s.clear();
for(int i = mi; i < hi; ++i) {
suf[i] = suf[i - 1];
auto it = s.upper_bound(w[i]);
if(it != s.end()) { suf[i] = max(suf[i], w[i] + *(it)); }
for(pii j : mxq[i]) {
int mx = max(prf[l[j.Y]], suf[i]);
auto it = s.lower_bound(j.X);
if(it != s.begin()) {
mx = max(mx, j.X + *prev(it));
}
deb("%d, %d %d %d\n", j.X, prf[l[j.Y]], mx, suf[i]);
ans[j.Y] = mx > k[j.Y];
}
s.insert(w[i]);
mxq[i].clear();
}
s.clear();
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) { scanf("%d", w + i); }
for(int i = 0; i < m; ++i) {
int r;
scanf("%d%d%d", l + i, &r, k + i);
q[l[i]].PB({r, i});
}
for(int i = 1; i <= n; ++i) {
sort(q[i].begin(), q[i].end());
}
dnc(1, n + 1);
for(int i = 0; i < m; ++i) printf("%d\n", ans[i] ^ 1);
return 0;
}
Compilation message (stderr)
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:81:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | for(int i = 1; i <= n; ++i) { scanf("%d", w + i); }
| ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d%d", l + i, &r, k + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |