#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(1e6)+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 = 5;
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;
int mxpref = 0;
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);
for(int j = r; j >= i; j --) {
int mx = get(i, j - 1);
if(mx > w[j]) {
if(j < r) mxsuf[j] = max(mxsuf[j + 1], mx + w[j]);
else mxsuf[j] = mx + w[j];
}
}
}
}
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 = -1;
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;
}
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 = -1;
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;
}
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:56:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
56 | sta[j][i] = max(sta[j-1][i], sta[j-1][i+(1<<j-1)]);
| ~^~
sortbooks.cpp:49:6: warning: unused variable 'mxpref' [-Wunused-variable]
49 | int mxpref = 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); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
11096 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
21340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
11096 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
21340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3023 ms |
90452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3044 ms |
48280 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
11096 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
21340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
11096 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
21340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
