제출 #889895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889895		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	2221 ms	100048 KiB

sortbooks

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