#include "bits/stdc++.h"
using namespace std;
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
void IOIGold2024_InshAllah() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
ll binmul(ll a, ll b, ll c) { ll res = 0; while(b) { if(b&1) (res += a) %= c; (a += a) %= c; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll c) { ll res = 1; while(b) { if(b&1) (res *= a) %= c; (a *= a) %= c; b >>= 1; } return res; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ld rnd() { return rng()%INT_MAX*1.0/INT_MAX; }
const ll inf = 1e18+7, MX = LLONG_MAX, MN = LLONG_MIN;
const ll mod = 1e9+7, N = 1e6+5;
#define ll int
struct sn { ll l, r, k; } b[N];
ll a[N], t[N][20], lg[N], res[N], bsz;
vector<ll> g[N];
ll get(ll l, ll r) {
if(l>r) return 0;
ll k = lg[r-l+1];
return max(t[l][k], t[r-(1<<k)+1][k]);
}
void kigash() {
ll n, q;
cin>>n>>q, bsz = min(n, 800);
ll mx = 0, mn = MX;
for(ll i=1; i<=n; i++) {
if(i>1) lg[i] = lg[i/2]+1;
cin>>a[i], t[i][0] = a[i];
mn = min(mn, a[i]);
if(a[i]<mx) res[(i+bsz-1)/bsz] = max(res[(i+bsz-1)/bsz], a[i]+mx);
mx = max(mx, a[i]);
g[(i+bsz-1)/bsz].pb(a[i]);
if(i%bsz==0) mx = 0;
}
for(ll i=1; i<=n; i++) sort(all(g[i]));
for(ll j=1; j<20; j++) {
for(ll i=1; i+(1<<j)-1<=n; i++) {
t[i][j] = max(t[i][j-1], t[i+(1<<(j-1))][j-1]);
}
}
ll mxk = 0;
for(ll i=1; i<=q; i++) {
cin>>b[i].l>>b[i].r>>b[i].k;
mxk = max(mxk, b[i].k);
}
if(mxk<mn) {
set<pair<ll, ll>> st;
ll l = -1;
for(ll i=1; i<=n; i++) {
if(a[i]<a[i-1]) {
st.insert({l, i});
l = i;
}
}
st.insert({l, n});
for(ll i=1; i<=q; i++) {
ll l = b[i].l, r = b[i].r, k = b[i].k;
auto it = st.lower_bound({l+1, -1});
if(it==st.begin()) cout<<"0\n";
else {
pair<ll, ll> pos = *prev(it);
if(pos.ff<=l && pos.ss<=r) cout<<"1\n";
else cout<<"0\n";
}
}
}
return;
for(ll j=1; j<=q; j++) {
ll l, r, k, f = 0, mx = 0, i;
l = b[j].l, r = b[j].r, k = b[j].k, i = l;
for(i=l; i<=r && (i+bsz-1)/bsz==(l+bsz-1)/bsz; i++) {
if(a[i]<mx) f = max(f, a[i]+mx);
mx = max(mx, a[i]);
}
for(; i<=r && (i+bsz-1)/bsz!=(r+bsz-1)/bsz; i += bsz) {
f = max(f, res[(i+bsz-1)/bsz]);
mx = get(l, i-1);
ll pos = lower_bound(all(g[(i+bsz-1)/bsz]), mx)-g[(i+bsz-1)/bsz].begin()-1;
if(pos>-1) f = max(f, mx+g[(i+bsz-1)/bsz][pos]);
}
mx = get(l, i-1);
for(; i<=r; i++) {
if(a[i]<mx) f = max(f, a[i]+mx);
mx = max(mx, a[i]);
}
cout<<(f>k ? 0 : 1)<<"\n";
}
return;
}
signed main(/*Kigash Amir*/) {
// freopen("");
IOIGold2024_InshAllah();
ll tt = 1;
// cin>>tt;
for(ll i=1; i<=tt; i++) {
kigash();
}
}
Compilation message
sortbooks.cpp: In function 'void kigash()':
sortbooks.cpp:42:21: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
42 | ll mx = 0, mn = MX;
| ^~
sortbooks.cpp:74:40: warning: unused variable 'k' [-Wunused-variable]
74 | ll l = b[i].l, r = b[i].r, k = b[i].k;
| ^
sortbooks.cpp: In function 'void freopen(std::string)':
sortbooks.cpp:17:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:17:73: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
409 ms |
127940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
38232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
