#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
x += k;
x %= mod;
if (x < 0)
x += mod;
}
void del(int &x, int k)
{
x -= k;
x %= mod;
if (x < 0)
x += mod;
}
const int MAXN = 8000005; // n*(log(max(ai))+4)
namespace WaveletTree
{
// nenso -> build -> query
int n;
int arr[maxn], w[MAXN], nxt = 1, in = 0;
int lc[MAXN], rc[MAXN], l[MAXN], r[MAXN];
int b[MAXN];
const int from = 0, to = maxn;
vi nen;
void nenso()
{
fo(i, 1, n) nen.pb(arr[i]);
sort(all(nen));
nen.erase(unique(all(nen)), nen.end());
fo(i, 1, n) arr[i] = lower_bound(all(nen), arr[i]) - nen.begin();
}
void build(int psz = -1, bool f = 1, int pnd = -1, int nd = 1, int s = from, int e = to)
{
l[nd] = ++in, r[nd] = in - 1;
int midp = psz >> 1, mid = (s + e) >> 1, i1 = (nd == 1) ? n : r[pnd];
for (int i = (nd == 1) ? 1 : l[pnd]; i <= i1; i++)
if (nd == 1 || (f && w[i] <= midp) || (!f && w[i] > midp))
w[in] = (nd == 1) ? arr[i] : w[i], r[nd] = in,
b[in] = b[in - 1] + (w[in] <= mid), in++;
if (s == e)
return;
int sz = (nd == 1) ? n : r[nd] - l[nd] + 1;
if (b[r[nd]] - b[l[nd] - 1])
lc[nd] = ++nxt, build(s + e, 1, nd, lc[nd], s, mid);
if (b[r[nd]] - b[l[nd] - 1] != sz)
rc[nd] = ++nxt, build(s + e, 0, nd, rc[nd], mid + 1, e);
}
/*
note:
- w stores the array elements of each node
- b stores the prefix sum of frequency of elements <= mid of each node
- lc contains the node number of the left child of a node
- rc contains the node number of the right child of a node
- nxt is used to find the new node number to assign to a node
- in is used to allot space in the w array for each node
- [l[nd],r[nd]] is the range for elements of node nd in w and b
- psz is the number of elements in the parent of a node
- pnd is the parent of a node
- f is 1 if the current node is a left child, 0 otherwise
*/
// kth smallest element in range [l1,r1]
int kth(int l1, int r1, int k, int nd = 1, int s = from, int e = to)
{
if (s == e)
return s;
int mid = (s + e) >> 1;
int got = b[l[nd] + r1] - b[l[nd] + l1 - 1];
if (got >= k)
return kth(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid);
return kth(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k - got, rc[nd], mid + 1, e);
}
int KTH(int l, int r, int k)
{
return nen[kth(l, r, k)];
}
// count of k in range [l1,r1]
int count(int l1, int r1, int k, int nd = 1, int s = from, int e = to)
{
if (s == e)
return b[l[nd] + r1] - b[l[nd] + l1 - 1];
int mid = (s + e) >> 1;
if (mid >= k)
return count(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid);
return count(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k, rc[nd], mid + 1, e);
}
int COUNT(int l, int r, int k)
{
k = lower_bound(all(nen), k) - nen.begin() + 1;
return count(l, r, k);
}
// count of numbers <= to k in range [l1,r1]
int lte(int l1, int r1, int k, int nd = 1, int s = from, int e = to)
{
if (l1 > r1 || k < s)
return 0;
if (e <= k)
return r1 - l1 + 1;
int mid = (s + e) >> 1;
return lte(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid) + lte(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k, rc[nd], mid + 1, e);
}
int LTE(int l, int r, int k)
{
k = upper_bound(all(nen), k) - nen.begin() - 1;
return lte(l, r, k);
}
}
struct BIT
{
int t[maxn];
void up(int x, int val)
{
for (; x < maxn; x += lb(x))
maximize(t[x], val);
}
void clear(int x)
{
for (; x < maxn; x += lb(x))
t[x] = 0;
}
int get(int x)
{
int ans = 0;
for (; x; x -= lb(x))
maximize(ans, t[x]);
return ans;
}
} minn;
struct BIT1
{
int t[maxn];
void up(int x, int val)
{
for (; x; x -= lb(x))
maximize(t[x], val);
}
void clear(int x)
{
for (; x; x -= lb(x))
t[x] = 0;
}
int get(int x)
{
int ans = 0;
for (; x < maxn; x += lb(x))
maximize(ans, t[x]);
return ans;
}
} maxx;
int n, q, a[maxn];
int res[maxn];
int sum[maxn];
int maxl[maxn];
vi nen;
void calc(int l, int r, vector<array<int, 4>> qry)
{
int mid = l + r >> 1;
maxl[mid] = a[mid];
fod(i, mid - 1, l)
{
maxl[i] = max(maxl[i + 1], a[i]);
int lb = lower_bound(all(nen), a[i + 1]) - nen.begin() + 1;
minn.up(lb, a[i + 1]);
lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
sum[i] = minn.get(lb - 1) + a[i];
maximize(sum[i], sum[i + 1]);
}
fo(i, mid + 2, r)
{
int lb = lower_bound(all(nen), a[i - 1]) - nen.begin() + 1;
maxx.up(lb, a[i - 1]);
lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
sum[i] = maxx.get(lb + 1) + a[i];
maximize(sum[i], sum[i - 1]);
}
fod(i, mid, l)
{
int lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
minn.clear(lb);
}
fo(i, mid + 1, r)
{
int lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
maxx.clear(lb);
}
vector<array<int, 4>> ll, rr;
for (auto [l, r, val, id] : qry) if(l != r)
{
if (l < mid or r > mid)
{
if (max(sum[l], sum[r]) > val)
res[id] = 1;
else
{
int L = max(val - maxl[l], 0);
if (WaveletTree::lte(mid, r - 1, maxl[l] - 1) -
WaveletTree::lte(mid, r - 1, L) >
0)
res[id] = 1;
}
}
else if (r < mid)
ll.push_back({l, r, val, id});
else if (l > mid)
rr.push_back({l, r, val, id});
}
fod(i, mid, l) maxl[i] = 0;
if (l != r)
{
calc(l, mid, ll);
calc(mid + 1, r, rr);
}
}
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
WaveletTree::n = n;
fo(i, 1, n)
{
cin >> a[i];
nen.pb(a[i]);
WaveletTree::arr[i] = a[i];
}
sort(all(nen));
nen.erase(unique(all(nen)), nen.end());
WaveletTree::build();
vector<array<int, 4>> qry(q);
fo(i, 0, q - 1)
{
cin >> qry[i][0] >> qry[i][1] >> qry[i][2];
qry[i][3] = i + 1;
}
calc(1, n, qry);
fo(i, 1, q) cout << (res[i] ^ 1) << "\n";
}
Compilation message
sortbooks.cpp: In function 'void calc(int, int, std::vector<std::array<int, 4> >)':
sortbooks.cpp:202:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
202 | int mid = l + r >> 1;
| ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:259:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
259 | main()
| ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:264:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
264 | freopen(name ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:265:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
265 | freopen(name ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
248 ms |
169456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
319 ms |
22460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
