#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#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("unroll-loops")
#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("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#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("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#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("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
const int mxN = 1e6 + 50;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ld EPS = 1e-9;
struct Node {
vector<ll> vec;
ll mx = 0, bad_mx = 0;
};
Node seg[mxN * 4];
ll ar[mxN];
Node dummy_node;
ll calc1(ll node) {
ll lft_max = seg[node * 2 + 1].mx;
auto it = upper_bound(all(seg[node * 2 + 2].vec), lft_max);
if (it == seg[node * 2 + 2].vec.begin()) {
return -lft_max;
} else {
--it;
return *it + lft_max;
}
}
Node left_right_mrg(Node lft, Node rgt) {
ll lft_max = lft.mx;
auto it = upper_bound(all(rgt.vec), lft_max);
ll ans = -lft_max;
if (it != rgt.vec.begin()) {
--it;
ans = *it + lft_max;
}
Node curr;
curr.bad_mx = max({lft.bad_mx, ans, rgt.bad_mx});
merge(all(lft.vec), all(rgt.vec), back_inserter(curr.vec));
curr.mx = max(lft.mx, rgt.mx);
return curr;
}
void build(ll node, ll start, ll end) {
if (start == end) {
seg[node].vec.pb(ar[start]);
seg[node].mx = ar[start];
seg[node].bad_mx = 0;
return;
}
ll mid = start + (end - start) / 2;
build(node * 2 + 1, start, mid);
build(node * 2 + 2, mid + 1, end);
merge(all(seg[node * 2 + 1].vec), all(seg[node * 2 + 2].vec), back_inserter(seg[node].vec));
seg[node].bad_mx = max({seg[node * 2 + 1].bad_mx, seg[node * 2 + 2].bad_mx, calc1(node)});
seg[node].mx = max(seg[node * 2 + 1].mx, seg[node * 2 + 2].mx);
}
Node qry(ll nd, ll start, ll end, ll l, ll r) {
if (start > r || end < l) return dummy_node;
if (start >= l && end <= r) return seg[nd];
ll mid = start + (end - start) / 2;
Node lft = qry(nd * 2 + 1, start, mid, l, r);
Node rgt = qry(nd * 2 + 2, mid + 1, end, l, r);
if (lft.mx == -1) return rgt;
else if (rgt.mx == -1) return lft;
return left_right_mrg(lft, rgt);
}
void solve() {
ll n, l, r, w, q;
cin >> n >> q;
for (ll i = 0; i < n; ++i) {
cin >> ar[i];
}
dummy_node.mx = -1;
build(0, 0, n - 1);
while (q--) {
cin >> l >> r >> w;
cout << (qry(0, 0, n - 1, l - 1, r - 1).bad_mx <= w) << nl;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
sortbooks.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
25 | #pragma GCC optimize("-fwhole-program")
| ^
sortbooks.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize("-fstrict-overflow")
| ^
sortbooks.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
34 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
sortbooks.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
48 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
sortbooks.cpp:79:17: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
79 | ll calc1(ll node) {
| ^
sortbooks.cpp:79:17: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:79:17: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:79:17: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:92:39: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
92 | Node left_right_mrg(Node lft, Node rgt) {
| ^
sortbooks.cpp:92:39: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:92:39: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:92:39: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:111:37: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
111 | void build(ll node, ll start, ll end) {
| ^
sortbooks.cpp:111:37: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:111:37: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:111:37: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:127:45: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
127 | Node qry(ll nd, ll start, ll end, ll l, ll r) {
| ^
sortbooks.cpp:127:45: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:127:45: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:127:45: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:138:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
138 | void solve() {
| ^
sortbooks.cpp:138:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:138:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:138:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:152:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
152 | signed main() {
| ^
sortbooks.cpp:152:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:152:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:152:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
158492 KB |
Output is correct |
| 2 |
Correct |
51 ms |
158288 KB |
Output is correct |
| 3 |
Correct |
50 ms |
158532 KB |
Output is correct |
| 4 |
Correct |
59 ms |
158424 KB |
Output is correct |
| 5 |
Correct |
58 ms |
158420 KB |
Output is correct |
| 6 |
Correct |
57 ms |
158544 KB |
Output is correct |
| 7 |
Correct |
55 ms |
158548 KB |
Output is correct |
| 8 |
Correct |
50 ms |
158516 KB |
Output is correct |
| 9 |
Correct |
53 ms |
158548 KB |
Output is correct |
| 10 |
Incorrect |
52 ms |
158548 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
158492 KB |
Output is correct |
| 2 |
Correct |
51 ms |
158288 KB |
Output is correct |
| 3 |
Correct |
50 ms |
158532 KB |
Output is correct |
| 4 |
Correct |
59 ms |
158424 KB |
Output is correct |
| 5 |
Correct |
58 ms |
158420 KB |
Output is correct |
| 6 |
Correct |
57 ms |
158544 KB |
Output is correct |
| 7 |
Correct |
55 ms |
158548 KB |
Output is correct |
| 8 |
Correct |
50 ms |
158516 KB |
Output is correct |
| 9 |
Correct |
53 ms |
158548 KB |
Output is correct |
| 10 |
Incorrect |
52 ms |
158548 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
258 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
183644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
158492 KB |
Output is correct |
| 2 |
Correct |
51 ms |
158288 KB |
Output is correct |
| 3 |
Correct |
50 ms |
158532 KB |
Output is correct |
| 4 |
Correct |
59 ms |
158424 KB |
Output is correct |
| 5 |
Correct |
58 ms |
158420 KB |
Output is correct |
| 6 |
Correct |
57 ms |
158544 KB |
Output is correct |
| 7 |
Correct |
55 ms |
158548 KB |
Output is correct |
| 8 |
Correct |
50 ms |
158516 KB |
Output is correct |
| 9 |
Correct |
53 ms |
158548 KB |
Output is correct |
| 10 |
Incorrect |
52 ms |
158548 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
158492 KB |
Output is correct |
| 2 |
Correct |
51 ms |
158288 KB |
Output is correct |
| 3 |
Correct |
50 ms |
158532 KB |
Output is correct |
| 4 |
Correct |
59 ms |
158424 KB |
Output is correct |
| 5 |
Correct |
58 ms |
158420 KB |
Output is correct |
| 6 |
Correct |
57 ms |
158544 KB |
Output is correct |
| 7 |
Correct |
55 ms |
158548 KB |
Output is correct |
| 8 |
Correct |
50 ms |
158516 KB |
Output is correct |
| 9 |
Correct |
53 ms |
158548 KB |
Output is correct |
| 10 |
Incorrect |
52 ms |
158548 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
