oj.uz

답안 #690384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
690384 2023-01-30T07:03:59 Z iskhakkutbilim Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
21 / 100
 3000 ms 14056 KB 
#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; j < sub.size(); j++){
					if(mn > sub[j]){
						idx = j, mn = sub[j];
					}
				}
				if(idx==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:22: 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; j < sub.size(); j++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 420 KB Output is correct
7 Correct 11 ms 368 KB Output is correct
8 Correct 22 ms 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 420 KB Output is correct
7 Correct 11 ms 368 KB Output is correct
8 Correct 22 ms 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct
11 Correct 355 ms 432 KB Output is correct
12 Execution timed out 3075 ms 640 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 407 ms 13968 KB Output is correct
2 Correct 423 ms 13940 KB Output is correct
3 Correct 413 ms 14012 KB Output is correct
4 Correct 413 ms 13944 KB Output is correct
5 Correct 465 ms 14056 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3066 ms 1980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 420 KB Output is correct
7 Correct 11 ms 368 KB Output is correct
8 Correct 22 ms 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct
11 Correct 355 ms 432 KB Output is correct
12 Execution timed out 3075 ms 640 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 420 KB Output is correct
7 Correct 11 ms 368 KB Output is correct
8 Correct 22 ms 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct
11 Correct 355 ms 432 KB Output is correct
12 Execution timed out 3075 ms 640 KB Time limit exceeded
13 Halted 0 ms 0 KB -