Submission #690379

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
690379	2023-01-30T07:02:39 Z	iskhakkutbilim	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	3000 ms	15928 KB

sortbooks

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e6;
int n, q;
int a[N], pref[N], sum[N];
int get_sum(int l,int r){
	return (sum[r] - (l > 0 ? sum[l-1] : 0));
}

main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> q;
	int mn = INT_MAX;
	for(int i = 0;i < n; i++){
		cin >> a[i];
		sum[i] = a[i] + (i > 0 ? sum[i-1] : 0);
		mn = min(mn, a[i]);
	}
	for(int i = 0;i < n-1; i++){
		if(i == 0){
			pref[i] = (a[i+1]>=a[i]);
		}else{
			pref[i] = pref[i-1]+ (a[i+1]>= a[i]);
		}
	}
	while(q--){
		int l, r, k; cin >> l >> r >> k; l--, r--;
		if(r==l){
			cout << 1 << '\n';
			continue;
		}
		if(mn > k){
		 	if(pref[r-1] -(l > 0 ? pref[l-1] : 0) == r-l){
		 		cout << 1;
			 }else{
			 	cout << 0;
			 }
		}else{
			vector<int> sub;
			for(int i = l;i <= r; i++){
				sub.push_back(a[i]);
			}
			int ok = 1;
			for(int i = 0;i < sub.size(); i++){
				int mn = INT_MAX, idx = -1;
				for(int j = i+1; j < sub.size(); j++){
					if(mn > sub[j]){
						idx = j, mn = sub[j];
					}
				}
				if(mn == sub[i] or mn  == INT_MAX) continue;
				for(int j = idx-1; j >= i; j--){
					if(sub[idx]+sub[j] <= k){
						swap(sub[idx], sub[j]);
						idx = j;
					}
				}
				if(sub[i] != mn){
					ok = 0;
					break;
				}
			}	
			if(ok) cout << 1;
			else cout << 0;
		}
		cout << '\n';
	}
	return 0;
}

Compilation message

sortbooks.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(int i = 0;i < sub.size(); i++){
      |                  ~~^~~~~~~~~~~~
sortbooks.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int j = i+1; j < sub.size(); j++){
      |                      ~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	440 ms	15928 KB	Output is correct
2	Correct	479 ms	15140 KB	Output is correct
3	Correct	489 ms	15120 KB	Output is correct
4	Correct	467 ms	15128 KB	Output is correct
5	Correct	454 ms	14880 KB	Output is correct