#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353; // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(1e5)+10;
const long long inf = 2e18;
const long double eps = 1e-15L;
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
const int B = 50;
int n, m, w[N], sta[20][N], LOG[N], mxsuf[N];
//int ql[N], qr[N], qk[N]
int get(int l, int r) {
if(l > r) return 0;
int j = LOG[r - l + 1];
return max(sta[j][l], sta[j][r-(1<<j)+1]);
}
void Baizho() {
for(int i = 2; i < N; i ++) LOG[i] = LOG[i / 2] + 1;
cin>>n>>m;
for(int i = 1; i <= n; i ++) {
cin>>w[i];
sta[0][i] = w[i];
}
for(int j = 1; j <= 19; j ++) {
for(int i = 1; i+(1<<j)-1 <= n; i ++) {
sta[j][i] = max(sta[j-1][i], sta[j-1][i+(1<<j-1)]);
}
}
for(int i = 1; i <= n; i ++) {
if(i % B == 1) {
int r = min(n, i + B - 1), mx = 0, ans = 0;
for(int j = i; j <= r; j ++) {
if(mx > w[j]) mxsuf[j] = mx + w[j];
mx = max(mx, w[j]);
}
for(int j = r - 1; j >= i; j --) mxsuf[j] = max(mxsuf[j], mxsuf[j + 1]);
}
}
// for(int i = 1; i <= n; i ++) cout<<mxsuf[i]<<" ";
// cout<<"\n";
while(m --) {
int l, r, k; cin>>l>>r>>k;
int bl = (l - 1) / B, br = (r - 1) / B;
if(bl == br) {
int mx = 0, ans = 0;
for(int i = l; i <= r; i ++) {
if(mx > w[i]) ans = max(ans, w[i] + mx);
mx = max(mx, w[i]);
}
cout<<(ans <= k)<<"\n";
continue;
}
int ans = 0, mx = 0;
for(int i = l; i <= bl * B + B; i ++) {
if(mx > w[i]) ans = max(ans, w[i] + mx);
mx = max(mx, w[i]);
}
for(int b = bl + 1; b < br; b ++) {
int pos = b * B;
for(int binl = b * B + 1, binr = b * B + B; binl <= binr; ) {
int mid = (binl + binr) / 2;
if(get(b * B + 1, mid) < mx) binl = mid + 1, pos = mid;
else binr = mid - 1;
}
if(pos >= b * B + 1) ans = max(ans, get(b * B + 1, pos) + mx);
if(pos < b * B + B) ans = max(ans, mxsuf[pos + 1]);
mx = max(mx, get(b * B + 1, b * B + B));
}
int pos = br * B;
for(int binl = br * B + 1, binr = r; binl <= binr; ) {
int mid = (binl + binr) / 2;
if(get(br * B + 1, mid) < mx) binl = mid + 1, pos = mid;
else binr = mid - 1;
}
if(pos >= br * B + 1) ans = max(ans, get(br * B + 1, pos) + mx);
if(pos < r) ans = max(ans, mxsuf[pos + 1]);
cout<<(ans <= k)<<"\n";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int ttt = 1;
// cin>>ttt;
for(int i=1; i<=ttt; i++) { Baizho(); }
}
Compilation message
sortbooks.cpp: In function 'void Baizho()':
sortbooks.cpp:55:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
55 | sta[j][i] = max(sta[j-1][i], sta[j-1][i+(1<<j-1)]);
| ~^~
sortbooks.cpp:60:39: warning: unused variable 'ans' [-Wunused-variable]
60 | int r = min(n, i + B - 1), mx = 0, ans = 0;
| ^~~
sortbooks.cpp: In function 'void Freopen(std::string)':
sortbooks.cpp:34:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:34:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
856 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
856 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
2904 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1242 ms |
9300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
856 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
856 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2772 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
