#include <bits/stdc++.h>
using namespace std;
/*
#pragma GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define popcount __builtin_popcount
#define endl '\n'
#define int long long
const long double Eps = 1e-12;
const int max1 = 2e9*1.4;
const int min1 = -1e9 *1.4;
const ll mod1 = 1000000007;
const ll mod2 = 2000000011;
const ll mod3 = 3000000017;
const ll mod = 998244353;
const int N = 1e6 + 100;
const int B = 4e6 + 100;
const ll INF = 3e18 + 100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll x,ll y,ll md) {
if(y == 0) return 1;
if(y == 1) return x;
if(y % 2 == 0) {
ll now = binpow(x,y/2,md);
return (1ll*now*now) % md;
}
else {
ll now = binpow(x,y/2,md);
return (1ll*((1ll*now*now) % md)*x) % md;
}
}
/*
for(int l = 0;l < logn - 1;l++) {
for(int i = 0;i + (2 << l) <= n;i++) {
sp[l + 1][i] = merge(sp[l][i],sp[l][i + (1 << l)]);
}
}
int rmq(int l,int r) {
int t = log2(r - l);
return merge(sp[t][l],sp[t][r - (1 << t)]);
}
*/
int n,q;
int a[N];
int tree[B];
int tree2[B];
int p[B];
void update2(int ind,int tl,int tr,int v,int x) {
if(tl == tr) {
tree2[v] = max(tree2[v],x);
return;
}
int middle = (tl + tr)/2;
if(middle >= ind) {
update2(ind,tl,middle,v + v,x);
}
else {
update2(ind,middle + 1,tr,v + v + 1,x);
}
tree2[v] = max(tree2[v + v],tree2[v + v + 1]);
}
void build(int tl,int tr,int v) {
if(tl == tr) {
tree2[v] = 0;
return;
}
int middle = (tl + tr)/2;
build(tl,middle,v + v);
build(middle + 1,tr,v + v + 1);
tree2[v] = max(tree2[v + v],tree2[v + v + 1]);
}
int getind(int l,int r,int tl,int tr,int v) {
if(l > r) return 0;
if(l > tr || tl > r) return 0;
if(l <= tl&&tr <= r) return tree2[v];
int middle = (tl + tr)/2;
return max(getind(l,r,tl,middle,v + v),getind(l,r,middle + 1,tr,v + v + 1));
}
void update(int ind,int x,int tl,int tr,int v) {
if(tl == tr) {
tree[v] = max(tree[v],x);
return;
}
int middle = (tl + tr)/2;
if(middle >= ind) update(ind,x,tl,middle,v + v);
else update(ind,x,middle + 1,tr,v + v + 1);
tree[v] = max(tree[v + v],tree[v + v + 1]);
}
int get(int l,int r,int tl,int tr,int v) {
if(l > tr || tl > r) return 0;
if(l <= tl&&tr <= r) return tree[v];
int middle = (tl + tr)/2;
return max(get(l,r,tl,middle,v + v),get(l,r,middle + 1,tr,v + v + 1));
}
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1;i <= n;i++) cin >> a[i];
pair <int,pair <int,pair <int,int> > > p[q + 1];
for(int i = 1;i <= q;i++) cin >> p[i].s.f >> p[i].f >> p[i].s.s.f;
for(int i = 1;i <= q;i++) p[i].s.s.s = i;
sort(p + 1,p + q + 1);
int it = 1;
int ans[q + 1] = {};
map <int,int> fnd;
int temp = 1;
set <int> s;
for(int i = 1;i <= n;i++) s.insert(a[i]);
for(auto x:s) {
fnd[x] = temp;
temp++;
}
build(1,temp,1);
for(int i = 1;i <= q;i++) {
int r = p[i].f;
while(it <= r) {
int ind = getind(fnd[a[it]] + 1,temp,1,temp,1);
update2(fnd[a[it]],1,temp,1,i);
if(ind != 0) {
update(ind,a[ind] + a[it],1,n,1);
}
it++;
}
int l = p[i].s.f;
int s = p[i].s.s.f;
int ind = p[i].s.s.s;
ans[ind] = (s >= get(l,r,1,n,1));
}
for(int i = 1;i <= q;i++) cout << ans[i] << endl;
}
/*
Lxner & WENARO
Лед
-------------------------------------------------------------------
Вс-все твои слёзы просто превращаю в лёд (В лёд)
Я спрячу сердце, его никто не найдёт
Не-не-не-не-не вижу смысла кончить этот эпизод
Я-я-я вижу выход, но не могу найти вход (—Ход-ход-ход-ход-ход, вход)
Все твои слёзы просто превращаю в лёд
Я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
Не вижу смысла кончить этот эпизод (Лё-ё-ёд)
Я вижу выход, но не могу найти вход (И-и)
Все твои слёзы просто превращаю в лё-лё-лёд
Я спрячу сердце, его никто не найдёт (Я-я)
Не вижу смысла кончить этот эпизод
Я вижу выход, но не могу найти вход
Мно-мно-много говоришь — пустые слова (—Ва-ва-ва)
Самый одинокий парень я — навсегда
Ка-ка-как бы ни хотел, но ты одна нужна
Боль и слёзы, да, бывает, иногда (Лёд, лёд)
Все твои слёзы просто превращаю в лё-лё-лёд
Я спрячу сердце, его никто не найдёт (А-а-а-а-а)
Бывает больно, но я знаю всё пройдёт (Всё пройдёт)
Я вижу выход, но не могу найти вход (А-а)
Все твои слёзы просто превращаю в лё-лё-лёд
Я спрячу сердце, его никто не найдёт (Лё-лё-лё-лё-лёд)
Бывает больно, но я знаю всё пройдёт (Всё пройдёт)
Я вижу выход, но не могу найти вход (—Ход-ход-ход-ход, вход)
И не растопишь, и не сможешь забыть (За-а-а-а—)
Где-то без меня нашла новую жизнь
Тебя так манит этот холодный мир
И-и-и-и-и ты как айсберг, ведь я снова разбит
It's so hard, это сложно
О-о-она застыла в ожидании солнца-а-а-а
Но я не думаю что сможет согреть
Её ледяную душу, остаётся лишь смотреть (А, а, а-а-а-а)
Все твои слёзы просто превращаю в лёд
Я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
Не вижу смысла кончить этот эпизод (—З-з-з-од)
Я вижу выход, но не могу найти вход (И-и)
Все твои слёзы просто превращаю в лё-лё-лёд
Я-я спрячу сердце, его никто не найдёт
Не вижу смысла кончить этот эпизод
Я вижу выход, но не могу найти вход
Твои слёзы просто-просто пре— в лёд
Я-я-я-я прячу сердце, его-его не найдёт (Не найд—, не най—)
Не вижу смысла кончить-кончить эпизод (А-а-а-а, а-а-а-а)
Я вижу выход, но не—, но не— найти вход
(—Ход-ход-ход-ход-ход, вход) Все твои слёзы просто превращаю в лёд
Я-я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
Не вижу смысла кончить этот эпизод (—З-з-з-од)
Я вижу выход, но не могу-гу най— вход
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3104 ms |
184336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
13064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
