#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 int long long
#define inf (int)1e18
#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 suml[maxn],sumr[maxn];
int maxl[maxn];
vi nen;
void calc(int l,int r,vector<array<int,4>> qry)
{
int mid = l + r >> 1;
fod(i,mid,l)
{
maxl[i] = max(maxl[i + 1],a[i]);
int lb = lower_bound(all(nen),a[i]) - nen.begin() + 1;
suml[i] = minn.get(lb) + a[i];
maximize(suml[i],suml[i + 1]);
minn.up(lb,a[i]);
}
fo(i,mid + 1,r)
{
int lb = lower_bound(all(nen),a[i]) - nen.begin() + 1;
sumr[i] = maxx.get(lb) + a[i];
maximize(sumr[i],sumr[i - 1]);
maxx.up(lb,a[i]);
}
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 <= mid and r >= mid)
{
if(max(suml[l],sumr[r]) > val) res[id] = 1;
else
{
int L = max(val - maxl[l],0ll);
if(WaveletTree::lte(mid,r - 1,maxl[l]) - 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);
// cout << WaveletTree::lte(0,4,8);en;
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(long long int, long long int, std::vector<std::array<long long int, 4> >)':
sortbooks.cpp:196:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
196 | int mid = l + r >> 1;
| ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:245:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
245 | main()
| ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:250:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
250 | freopen(name ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:251:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
251 | freopen(name ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 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 |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2004 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
308 ms |
52476 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 |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 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 |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
