Submission #889793

#	Time	Username	Problem	Language	Result	Execution time	Memory
889793		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	57 ms	97364 KiB

sortbooks

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5001;
int a[N], pref[N];
int ans[N][N];
int main(){
	int n, q;
	cin >> n >> q;
	a[0]=1e9+7;
	
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	for(int i=1; i<=n; i++) {
		pref[i]=i-1;
		while(a[i]>=a[pref[i]]) {
			pref[i]=pref[pref[i]];
		}
	}
	for(int i=1; i<=n; i++){
		ans[i][i]=0;
		for(int j=i+1; j<=n; j++){
			ans[i][j]=ans[i][j-1];
			if(pref[j]>=i){
				ans[i][j]=max(ans[i][j], a[pref[j]] + a[j]);
			}
		}
	}
	while(q--){
		int l, r, k;
		cin >> l >> r >> k;
		if(ans[l][r]<=k){
			cout<<"1\n";
		}
		else{
			cout<<"0\n";
		}
	}
}

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