#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 20;
const llong INF = 4e18;
const int INTINF = 2e9;
int n, q;
struct Sparse
{
int sparse[MAXLOG][MAXN];
int getLog[MAXN];
void build(int a[])
{
for (int i = 1 ; i <= n ; ++i)
{
sparse[0][i] = a[i];
}
for (int log = 1 ; (1 << log) <= n ; ++log)
{
for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
{
sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
}
}
for (int i = 1 ; i <= n ; ++i)
{
getLog[i] = getLog[i - 1];
if ((1 << getLog[i] + 1) < i) getLog[i]++;
}
}
int findMAX(int l, int r)
{
if (l > r) return 0;
int log = getLog[r - l + 1];
return std::max(sparse[log][l], sparse[log][r - (1 << log) + 1]);
}
};
struct Fenwick
{
int tree[MAXN];
void update(int pos, int value)
{
for (int idx = pos ; idx <= n ; idx += idx & (-idx))
{
tree[idx] += value;
}
}
int query(int pos)
{
int res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
void reset(int pos)
{
update(pos, -query(pos) + query(pos - 1));
}
int findKth(int k)
{
int pos = 0;
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (pos + (1 << log) <= n && tree[pos + (1 << log)] < k)
{
pos += (1 << log);
k -= tree[pos];
}
}
return pos + 1;
}
};
struct SegmentTree
{
int tree[4*MAXN];
void update(int l, int r, int node, int queryPos, int queryVal)
{
if (l == r)
{
tree[node] = queryVal;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = std::max(tree[2*node], tree[2*node + 1]);
}
int query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
int res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res = std::max(res, query(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = std::max(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void update(int pos, int val)
{
update(1, n, 1, pos, val);
}
int query(int l, int r)
{
return query(1, n, 1, l, r);
}
};
struct Query
{
int l, r, k, idx;
friend bool operator > (const Query &a, const Query &b)
{
return a.k > b.k;
}
};
int a[MAXN];
int perm[MAXN];
bool answer[MAXN];
Query query[MAXN];
SegmentTree tree;
Fenwick active;
Fenwick sorted;
Sparse sparse;
void addNum(int idx)
{
int cntTo = active.query(idx - 1);
if (cntTo > 0)
{
int prev = active.findKth(cntTo);
sorted.reset(prev);
sorted.update(prev, (a[prev] > a[idx]));
tree.update(prev, sparse.findMAX(prev + 1, idx - 1) + a[prev]);
}
if (active.query(n) == cntTo)
{
tree.update(idx, sparse.findMAX(idx + 1, n) + a[idx]);
} else
{
int next = active.findKth(cntTo + 1);
tree.update(idx, sparse.findMAX(idx + 1, next - 1) + a[idx]);
}
active.update(idx, 1);
}
void solve()
{
std::iota(perm + 1, perm + 1 + n, 1);
std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
{
return a[x] > a[y];
});
std::sort(query + 1, query + 1 + q, std::greater <Query> ());
int numsPtr = 0;
for (int i = 1 ; i <= q ; ++i)
{
auto [l, r, k, idx] = query[i];
while (numsPtr + 1 <= n && a[perm[numsPtr + 1]] >= (k + 2) / 2)
{
numsPtr++;
addNum(perm[numsPtr]);
}
int toL = active.query(l - 1);
int toR = active.query(r);
if (toL == toR)
{
answer[idx] = true;
continue;
}
int posL = active.findKth(toL + 1);
int posR = active.findKth(toR);
if (sorted.query(posR - 1) - sorted.query(posL - 1) > 0)
{
answer[idx] = false;
continue;
}
int res = 0;
if (posR < r)
{
res = std::max(res, a[posR] + sparse.findMAX(posR + 1, r));
}
res = std::max(res, tree.query(posL, posR - 1));
answer[idx] = (res <= k);
}
}
void print()
{
for (int i = 1 ; i <= q ; ++i)
{
std::cout << answer[i] << '\n';
}
}
void input()
{
std::cin >> n >> q;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
for (int i = 1 ; i <= q ; ++i)
{
std::cin >> query[i].l >> query[i].r >> query[i].k;
query[i].idx = i;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}
Compilation message
sortbooks.cpp: In member function 'void Sparse::build(int*)':
sortbooks.cpp:34:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
34 | sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
| ~~~~^~~
sortbooks.cpp:41:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
41 | if ((1 << getLog[i] + 1) < i) getLog[i]++;
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1764 ms |
54632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
13652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
