Submission #1132615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132615		Agageldi	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	797 ms	10188 KiB

sortbooks

/*
ID: agageld1
LANG: C++17
TASK:
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 4000005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, t, a[N], l, r, x, mx, q, b[N];
vector <pair<int,int>> v;

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q;
	for(int i= 1;i<=n;i++) {
		cin >> a[i];
	}
	l = 1;
	for(int i = 2; i <= n; i++) {
		if(a[i] >= a[i - 1]) continue;
		v.pb({l, i - 1});
		l = i;
	}
	v.pb({l, n});
	for(int i = 1; i <= q; i++) {
		cin >> l >> r >> x;
		if(l == r) {
			cout << "1\n";
			continue;
		}
		auto p = lower_bound(v.begin(),v.end(),make_pair(l,r));
		if(p == v.end()) {
			cout << "0\n";
			continue;
		}
		if((*p).ff <= l && (*p).ss >= r) {
			cout << "1\n";
			continue;
		}
		if((*p).ff != v[0].ff || (*p).ss != v[0].ss) p--;
		if((*p).ff <= l && (*p).ss >= r) {
			cout << "1\n";
			continue;
		}
		mx = a[l];
		bool tr = 0;
		for(int j = l + 1; j <= r; j++) {
			if(mx > a[j] && mx + a[j] > x) {
				tr = 1;
				break;
			}
			mx = max(mx,a[j]);
		}
		if(tr) cout << "0\n";
		else cout << "1\n";
	}
}

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