#include <bits/stdc++.h>
using namespace std;
// need to get highest number which is in the wrong place
// and the lowest number
// [1]
// [1, 8]
// [1, 4, 8]
// [1, 2, 4, 8]
// once a number is out of place, it is like that for any addition
// so can add events for numbers being out of place
// it becomes out of place on the next smaller number to the right
// [3, 5, 1, 8, 2]
// [0, 0, 0, 0, 0] l=4
// [0, 0, 0, 0, 8] l=3
// [0, 0, 0, 0, 8] l=2
// [0, 0, 5, 0, 8] l=1
// [0, 0, 5, 0, 8] l=0
// so trivialis maximis?
const int inf = 1 << 30;
template <typename Info>
struct Tree {
vector<Info> info;
Tree(int size) { info.resize(size*4); }
void update(int v, int x, int xl, int xr, Info delta) {
if (xl == xr) {
info[x] = info[x].combine(delta);
} else {
int xm = (xl + xr) / 2;
if (v <= xm) update(v, x*2, xl, xm, delta);
else update(v, x*2+1, xm+1, xr, delta);
info[x] = info[x*2].combine(info[x*2+1]);
}
}
Info query(int l, int r, int x, int xl, int xr) {
if (l > r) return Info();
if (l == xl && r == xr) {
return info[x];
} else {
int xm = (xl + xr) / 2;
Info left = query(l, min(r, xm), x*2, xl, xm);
Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
return left.combine(right);
}
}
};
struct MinInfo {
int m;
MinInfo(int M) : m(M) {}
MinInfo() : m(1<<30) {}
MinInfo combine(MinInfo &other) { return {min(m, other.m)}; }
};
struct MaxInfo {
int m;
MaxInfo(int M) : m(M) {}
MaxInfo() : m(0) {}
MaxInfo combine(MaxInfo &other) { return {max(m, other.m)}; }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M;
cin >> N >> M;
vector<int> w(N);
for (int i=0; i<N; i++) cin >> w[i];
vector<int> next(N, -1);
stack<int> S;
for (int i=0; i<N; i++) {
while (S.size() && w[S.top()] > w[i]) {
next[S.top()] = i;
S.pop();
}
S.push(i);
}
vector<array<int,4>> queries(M);
for (int i=0; i<M; i++) {
int l, r, k;
cin >> l >> r >> k;
queries[i] = {{l-1, r-1, k, i}};
}
sort(queries.rbegin(), queries.rend());
Tree<MinInfo> minTree(N);
Tree<MaxInfo> maxTree(N);
vector<int> ans(M);
int line = N;
for (int i=0; i<M; i++) {
int l = queries[i][0], r = queries[i][1];
int k = queries[i][2], q = queries[i][3];
while (line > l) {
line--;
minTree.update(line, 1, 0, N-1, w[line]);
if (next[line] != -1) {
maxTree.update(next[line], 1, 0, N-1, w[line]);
}
}
int lo = minTree.query(l, r, 1, 0, N-1).m;
int hi = maxTree.query(l, r, 1, 0, N-1).m;
if (hi == 0 || lo + hi <= k) ans[q] = 1;
}
for (int x : ans) cout << x << "\n";
for (int i=0; i<N; i++) cout << minTree.query(i, i, 1, 0, N-1).m << " "; cout << "\n";
for (int i=0; i<N; i++) cout << maxTree.query(i, i, 1, 0, N-1).m << " "; cout << "\n";
return 0;
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:109:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
109 | for (int i=0; i<N; i++) cout << minTree.query(i, i, 1, 0, N-1).m << " "; cout << "\n";
| ^~~
sortbooks.cpp:109:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
109 | for (int i=0; i<N; i++) cout << minTree.query(i, i, 1, 0, N-1).m << " "; cout << "\n";
| ^~~~
sortbooks.cpp:110:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
110 | for (int i=0; i<N; i++) cout << maxTree.query(i, i, 1, 0, N-1).m << " "; cout << "\n";
| ^~~
sortbooks.cpp:110:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
110 | for (int i=0; i<N; i++) cout << maxTree.query(i, i, 1, 0, N-1).m << " "; cout << "\n";
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1507 ms |
77052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
6992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
