#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++){
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
- |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3066 ms |
1980 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
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 |
- |
# |
Verdict |
Execution time |
Memory |
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 |
- |