oj.uz

Submission #843076

# Submission time Handle Problem Language Result Execution time Memory
843076 2023-09-03T15:53:32 Z yahyobekabdunazarov Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 375 ms 51028 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
//... max1 .... max2
//... max2 .... max1
using namespace std;

const int maxn = 1e6 + 9;
int f[maxn];
void upd(int n){
    while(n < maxn){
        f[n]++;
        n += n & -n;
    }
}
int summa(int n){
    int sm = 0;
    while(n){
        sm += f[n];
        n -= n & -n;
    }
    return sm;
}
int summa(int l, int r){
    return summa(r) - summa(l);
}
void solve(){  
    int n, m;
    cin >> n >> m;
    int a[n + 1];
    a[0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] >= a[i - 1]) upd(i);
    }
    while(m--){
        int l, r, k, mx = 0, sum = 0, ok = 1;
        cin >> l >> r >> k;
        if(n <= 5000 && m <= 5000){
            for(int i = l; i <= r; i++){
                sum = max(sum, (a[i] + mx) * (a[i] < mx));
                mx = max(mx, a[i]);
            }
            cout << (sum <= k ? "1\n" : "0\n");
        }
        else{
            // 1 2 3 4
            // 2 1 2 3
            // 1 0 1 1
            cout << (summa(l, r) >= r - l ? "1\n" : "0\n");
        }
    }
}

int32_t main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int t = 1;  
    //cin >> t;
    while(t--){
        solve();
        cout << '\n';
    }

    return 0;
}

Compilation message

sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:40:39: warning: unused variable 'ok' [-Wunused-variable]
   40 |         int l, r, k, mx = 0, sum = 0, ok = 1;
      |                                       ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 4 ms 4444 KB Output is correct
12 Correct 8 ms 4444 KB Output is correct
13 Correct 9 ms 4656 KB Output is correct
14 Correct 15 ms 4444 KB Output is correct
15 Correct 15 ms 4660 KB Output is correct
16 Correct 29 ms 4444 KB Output is correct
17 Correct 22 ms 4648 KB Output is correct
18 Correct 27 ms 4656 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 18068 KB Output is correct
2 Correct 375 ms 50848 KB Output is correct
3 Correct 371 ms 50880 KB Output is correct
4 Correct 375 ms 51028 KB Output is correct
5 Correct 373 ms 51028 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 4 ms 4444 KB Output is correct
12 Correct 8 ms 4444 KB Output is correct
13 Correct 9 ms 4656 KB Output is correct
14 Correct 15 ms 4444 KB Output is correct
15 Correct 15 ms 4660 KB Output is correct
16 Correct 29 ms 4444 KB Output is correct
17 Correct 22 ms 4648 KB Output is correct
18 Correct 27 ms 4656 KB Output is correct
19 Incorrect 75 ms 6484 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 4 ms 4444 KB Output is correct
12 Correct 8 ms 4444 KB Output is correct
13 Correct 9 ms 4656 KB Output is correct
14 Correct 15 ms 4444 KB Output is correct
15 Correct 15 ms 4660 KB Output is correct
16 Correct 29 ms 4444 KB Output is correct
17 Correct 22 ms 4648 KB Output is correct
18 Correct 27 ms 4656 KB Output is correct
19 Correct 358 ms 18068 KB Output is correct
20 Correct 375 ms 50848 KB Output is correct
21 Correct 371 ms 50880 KB Output is correct
22 Correct 375 ms 51028 KB Output is correct
23 Correct 373 ms 51028 KB Output is correct
24 Incorrect 29 ms 5720 KB Output isn't correct
25 Halted 0 ms 0 KB -