// Problem: A - Hedgehog Daniyar and Algorithms
// Contest: Virtual Judge - IOI contest #3 (div 1 + 2)
// URL: https://vjudge.net/contest/610287#problem/A
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz size()
#define yes "YES"
#define no "NO"
#define ok "OK\n"
#define IOI ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pf push_front
#define pb push_back
#define S second
#define F first
using namespace std;
const int N = 1e6 + 5;
const int NN = 3e6 + 5;
const int mod = 1e9 + 7;
const int inf = 1e11;
int n, m;
int a[N], l[N], r[N], w[N], t[4 * N];
vector<int> b;
int pref[N];
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
return;
}
int mid = tl + tr >> 1;
build(v + v, tl, mid);
build(v + v + 1, mid + 1, tr);
t[v] = max(t[v + v], t[v + v + 1]);
}
int get(int v, int tl, int tr, int ll, int rr) {
if (rr < tl or tr < ll) {
return -1;
}
if (ll <= tl and tr <= rr) {
return t[v];
}
int mid = tl + tr >> 1;
return max(get(v + v, tl, mid, ll, rr), get(v + v + 1, mid + 1, tr, ll, rr));
}
void legenda_ne_umret() {
cin >> n >> m;
b.pb(0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i > 1) {
int cur = a[i] - a[i - 1];
if (cur >= 0) {
b.pb(1);
}
else b.pb(0);
}
pref[b.sz] = pref[b.sz - 1] + b.back();
}
build(1, 1, n);
for (int i = 1; i <= m; i++) {
cin >> l[i] >> r[i] >> w[i];
if (pref[r[i]] - pref[l[i]] == r[i] - l[i]) {
cout << 1 << '\n';
continue;
}
int mx = get(1, 1, n, l[i], r[i]);
if (mx > a[i]) {
if (mx + a[i] > w[i]) {
cout << 0 << '\n';
continue;
}
}
cout << 1 << '\n';
}
}
signed main() {
//IOI;
//freopen("haybales.in", "r", stdin);
//freopen("haybales.out", "w", stdout);
///////////////////////////////////////////
int t = 1;
//cin >> t;
for (int i = 1; i <= t; i++) {
//cout << "Case " << i << ":\n";
legenda_ne_umret();
cout << '\n';
}
}
Compilation message
sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = tl + tr >> 1;
| ~~~^~~~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = tl + tr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2910 ms |
68348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
20172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
