Submission #384161

#	Time	Username	Problem	Language	Result	Execution time	Memory
384161		patrikpavic2	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2926 ms	114852 KiB

sortbooks

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

#define PB push_back

using namespace std;

const int N = 1e6 + 500;
const int OFF = (1 << 20);

int T[2 * OFF], prop[2 * OFF];
int n, q, qL[N], qR[N], qK[N], qA[N], A[N];
vector < int > v[N];

void refresh(int x){
	if(!prop[x]) return;
	T[x] += prop[x];
	if(x < OFF){
		prop[2 * x] += prop[x];
		prop[2 * x + 1] += prop[x];
	}
	prop[x] = 0;
}

void update(int i, int a, int b, int lo, int hi,int x){
	refresh(i);
	if(lo <= a && b <= hi){
		prop[i] += x; refresh(i);
		return;
	}
	if(a > hi || b < lo) return;
	update(2 * i, a, (a + b) / 2, lo, hi, x);
	update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
	T[i] = max(T[2 * i], T[2 * i + 1]);
}

int query(int i, int a, int b, int lo, int hi){
	refresh(i);
	if(lo <= a && b <= hi) return T[i];
	if(a > hi || b < lo) return 0;
	return max(query(2 * i, a, (a + b) / 2, lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++)
		scanf("%d", A + i);
	for(int i = 0;i < q;i++){
		scanf("%d%d%d", qL + i, qR + i, qK + i);
		qL[i]--, qR[i]--; v[qL[i]].PB(i);
	}
	stack < int > S;
	for(int i = n - 1;i >= 0;i--){
		while(!S.empty () && A[i] > A[S.top()]){
			int vrh = S.top(); S.pop();
			update(1, 0, OFF - 1, vrh + 1, (S.empty() ? n : S.top()) - 1, A[i] - A[vrh]);
			update(1, 0, OFF - 1, vrh, vrh, A[i] + A[vrh]);
		}
		S.push(i);
		for(int x : v[i]){
			qA[x] = query(1, 0, OFF - 1, qL[x], qR[x]);
		}
	}
	for(int i = 0;i < q;i++)
		printf("%d\n", qA[i] <= qK[i]);
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d%d%d", qL + i, qR + i, qK + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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