oj.uz

Submission #889887

# Submission time Handle Problem Language Result Execution time Memory
889887 2023-12-20T09:09:47 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 4 ms 4604 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 4604 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Runtime error 3 ms 604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 4604 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Runtime error 3 ms 604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 4604 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Runtime error 3 ms 604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 4604 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Runtime error 3 ms 604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -