#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define pb push_back
#define F first
#define S second
#define lll unsigned long long
#define lld long double
#define data sdadsd
//#define int lll
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
const int N = 1e6 + 229;
const lll M = 1e9 + 7;
const lll M2 = 1e9 + 9;
const lll mod = 998244353;
const int rx[4] = {0, 0, -1, 1};
const int ry[4] = {-1, 1, 0, 0};
const lld eps = 1e-11;
const double pi = acos(-1.0);
int n;
int prec[N][20];
set < int > all[N][20];
int a[N];
vector < pair < int, int > > need;
void go(int l, int r, int st) {
if (r < l) {
return;
}
int now;
int mid;
while (st >= 0) {
now = (1 << st);
mid = r / now * now;
if (mid - now + 1 >= l) {
need.pb({mid, st});
if (st) {
go(l, mid - now, st);
go(mid + 1, r, st);
}
return;
}
--st;
}
return;
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen("maxxor.in", "r", stdin);
// freopen("maxxor.out", "w", stdout);
#endif
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
all[i][0].insert(a[i]);
}
int now;
int x;
for (int st = 1; st < 20; ++st) {
now = (1 << st);
for (int i = 1; i <= n; ++i) {
if (i % now) {
continue;
}
prec[i][st] = max(prec[i][st - 1], prec[i - now / 2][st - 1]);
x = *all[i - now / 2][st - 1].rbegin();
if (*all[i][st - 1].begin() < x) {
auto it = all[i][st - 1].lower_bound(x);
--it;
prec[i][st] = max(prec[i][st], x + *it);
}
for (int j = 0; j < now; ++j) {
all[i][st].insert(a[i - j]);
}
}
}
int l, r, k;
int res;
int best;
while (m--) {
cin >> l >> r >> k;
need.clear();
go(l, r, 19);
sort(need.begin(), need.end());
res = 0;
best = 0;
for (auto i : need) {
if (*all[i.F][i.S].begin() < best) {
auto it = all[i.F][i.S].lower_bound(best);
--it;
res = max(res, best + *it);
}
res = max(res, prec[i.F][i.S]);
best = max(best, *all[i.F][i.S].rbegin());
}
cout << (res <= k) << '\n';
}
return 0;
}
Compilation message
sortbooks.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
215 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
215 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
208 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
209 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
215 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
215 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
