Submission #1118872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118872		Zflop	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	2726 ms	247596 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NMAX = (int)1e6 + 50;
vector<vector<int>>L[NMAX];
int N,M,A[NMAX],ans[NMAX],add[NMAX * 4],mx[NMAX * 4],mx_adv[NMAX * 4],lazy[NMAX * 4];


void propagate(int dad,int node) {
	if (mx_adv[node] + lazy[dad] > mx[node] + add[node]) { 
		add[node] = lazy[dad];
		mx[node] = mx_adv[node];
		}
	lazy[node] = max(lazy[dad],lazy[node]);
	}

void laz(int x) {
	int left = x * 2;
	int right = x * 2 + 1;
	propagate(x,left);
	propagate(x,right);
	lazy[x] = 0;
	}

void make(int i,int v,int l,int r,int x) {
	laz(x);
	if (l == r) {
		mx[x] = v;
		mx_adv[x] = v;
		return;
		}
	int mid = (l + r) / 2;
	if (i <= mid) make(i,v,l,mid,2 * x);
	else make(i,v,mid + 1,r,2 * x + 1);
	if (mx[2 * x] + add[2 * x] > mx[2 * x + 1] + add[2 * x + 1]) {
		mx[x] = mx[2 * x];
		add[x] = add[2 * x];
		}
	else {
		mx[x] = mx[2 * x + 1];
		add[x] = add[2 * x + 1];
		}
	mx_adv[x] = max(mx_adv[2 * x],mx_adv[2 * x + 1]);
	}

int get_maxim(int a,int b,int l,int r,int x) {
	laz(x);
	if (a <= l && r <= b) 
		return add[x] + mx[x];
	if (r < a || b < l)
		return 0;
	int mid = (l + r) / 2;
	return max(get_maxim(a,b,l,mid,2 * x),get_maxim(a,b,mid + 1,r,2 * x + 1));
	}
void update(int a,int b,int v,int l,int r,int x) {
	laz(x);
	if (a <= l && r <= b) {
		if (mx_adv[x] + v > mx[x] + add[x]) {
			add[x] = max(add[x],v);
			mx[x] = mx_adv[x];
			}
		lazy[x] = v;
		return;
		}
	if (r < a || b < l) return;
	int mid = (l + r) / 2;
	update(a,b,v,l,mid,2 * x);
	update(a,b,v,mid + 1,r,2 * x + 1);
	if (mx[2 * x] + add[2 * x] > mx[2 * x + 1] + add[2 * x + 1]) {
		mx[x] = mx[2 * x];
		add[x] = add[2 * x];
		}
	else {
		mx[x] = mx[2 * x + 1];
		add[x] = add[2 * x + 1];
		}
	mx_adv[x] = max(mx_adv[2 * x],mx_adv[2 * x + 1]);
	}

void solve() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N;++i)
		cin >> A[i];
	for (int i = 1; i <= M;++i) {
		int l,r,k; cin >> l >> r >> k;
		L[l].push_back({r,k,i});
		}
	A[N + 1] = (int)1e9 * 2;
	stack<int>q;
	q.push(N + 1);
	for (int i = N; i;--i) {
		while (A[i] >= A[q.top()])
			q.pop();
		int j = q.top() - 1;
		q.push(i);
		update(i + 1,j,A[i],1,N,1);
		for (auto X : L[i])
			ans[X[2]] = (X[1] >= get_maxim(i,X[0],1,N,1));
		make(i,A[i],1,N,1);
		}
	for (int i = 1; i <= M;++i) {
		cout << ans[i] << '\n'; 
		//cout << i << ' ';
		}
	}


main() {
	solve();
	}

Compilation message (stderr)

sortbooks.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main() {
      | ^~~~

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