Submission #889886

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

sortbooks

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5001;
bool ok[N];	
int a[N], pref[N],mn=1e9+1, mnk=1e9+1;
int ans[N][N];
int main(){
	int n, q;
	cin >> n >> q;
	a[0]=1e9+7;
	
	ok[0]=1;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		if(ok[i-1] && a[i] >= a[i-1]){
			ok[i]=1;
		}
		mn=min(mn,a[i]);
	}
	int l[N],r[N],k[N];
	for(int i=1; i<=q; i++){
		cin>>l[i]>>r[i]>>k[i];
		mnk=min(mnk, k[i]);
	}
	
	if(mn>mnk){
		for(int i=1; i<=q; i++){
			bool ans=1;
			if(ok[r[i]]){
				cout<<ans<<"\n";
				continue;
			}
			for(int i=l[i]; i<r[i]; i++){
				if(a[i]>a[i+1]){
					ans=0;
					break;
				}
			}
			cout<<ans<<"\n";
		}
		return 0;
	}
	
	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";
		}
	}
	*/
	for(int i=1;i<=q; i++){
		if(ans[l[i]][r[i]]<=k[i]){
			cout<<"1\n";
		}
		else{
			cout<<"0\n";
		}
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:34:12: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |    for(int i=l[i]; i<r[i]; i++){
      |            ^

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