#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 = 4e6 + 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;
vector < vector < int > > all;
vector < int > ans;
vector < int > need;
int st;
void prec(int v, int l, int r) {
for (int i = l; i < min(r, n); ++i) {
if (i > l && all[(1 << st) + i].front() < all[v].back()) {
ans[v] = max(ans[v], all[(1 << st) + i].front() + all[v].back());
}
all[v].pb(all[(1 << st) + i].front());
}
sort(all[v].begin(), all[v].end());
if (l + 1 == r) {
return;
}
int mid = (l + r) / 2;
prec(v * 2, l, mid);
prec(v * 2 + 1, mid, r);
}
void go(int v, int l, int r, int cl, int cr) {
if (cl >= r || cr <= l) {
return;
}
if (cl >= l && cr <= r) {
need.pb(v);
return;
}
int mid = (cl + cr) / 2;
go(v * 2, l, r, cl, mid);
go(v * 2 + 1, l, r, mid, cr);
}
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 m;
cin >> n >> m;
while ((1 << st) < n) {
++st;
}
all.resize(1 << (st + 1));
ans.resize(1 << (st + 1));
int x;
for (int i = 0; i < n; ++i) {
cin >> x;
all[(1 << st) + i].pb(x);
}
prec(1, 0, 1 << st);
int l, r, k;
int res;
int best;
while (m--) {
cin >> l >> r >> k;
--l;
need.clear();
need.shrink_to_fit();
go(1, l, r, 0, 1 << st);
res = 0;
best = 0;
for (auto i : need) {
if (best > all[i].front()) {
auto it = lower_bound(all[i].begin(), all[i].end(), best) - all[i].begin();
--it;
res = max(res, best + all[i][it]);
}
best = max(best, all[i].back());
res = max(res, ans[i]);
}
cout << (res <= k) << '\n';
}
return 0;
}
Compilation message
sortbooks.cpp:78:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3016 ms |
204580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
384 ms |
20848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
