Submission #928275

#	Time	Username	Problem	Language	Result	Execution time	Memory
928275		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	2910 ms	68348 KiB

sortbooks

// 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 (stderr)

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;
      |            ~~~^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23