oj.uz

Submission #344381

# Submission time Handle Problem Language Result Execution time Memory
344381 2021-01-05T15:26:25 Z koketsu Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2549 ms 20588 KB 
#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int Mxn = 1e6 + 7;
const LL Mod = 1e9 + 7;
const LL Inf = 1e14 + 7;
const int K = 450;

int N, M, Mood[Mxn / K], W[Mxn], Max_value[Mxn / K];

vector <int> V[Mxn / K];

int main(){
    Kultivator;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        cin >> W[i];
    }
    for(int i = 0; i < N; i++){
        int Block_id = (i / K);

        Max_value[Block_id] = max(Max_value[Block_id], W[i]);
        V[Block_id].pb(W[i]);

        for(int j = i; j < (Block_id + 1) * K; j++){
            if(W[i] > W[j]){
                Mood[Block_id] = max(Mood[Block_id], W[i] + W[j]);
            }
        }
    }
    for(int i = 0; i <= (N - 1) / K; i++){
        sort(V[i].begin(), V[i].end());
    }
    while(M--){
        int L, R, X;
        cin >> L >> R >> X;
        L--, R--;
        int Mx = 0, Mxx = 0;
        for(int i = L; i <= R;){
            if(i % K == 0 && i + K <= R){
                int Block_id = i / K;
                Mx = max(Mx, Mood[Block_id]);

                int j = lower_bound(V[Block_id].begin(), V[Block_id].end(), Mxx) - V[Block_id].begin() - 1;
                if(j >= 0){
                    Mx = max(Mx, Mxx + V[Block_id][j]);
                }
                Mxx = max(Mxx, Max_value[Block_id]);
                i += K;
            } else {
                if(Mxx <= W[i]){
                    Mxx = W[i];
                } else {
                    Mx = max(Mx, Mxx + W[i]);
                }
                i++;
            }
        }
        if(Mx > X) cout << "0\n";
        else cout << "1\n";
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 5 ms 492 KB Output is correct
12 Correct 9 ms 492 KB Output is correct
13 Correct 8 ms 620 KB Output is correct
14 Correct 11 ms 620 KB Output is correct
15 Correct 11 ms 620 KB Output is correct
16 Correct 8 ms 620 KB Output is correct
17 Correct 6 ms 492 KB Output is correct
18 Correct 7 ms 492 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 779 ms 20588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 2540 KB Output is correct
2 Correct 700 ms 3208 KB Output is correct
3 Correct 368 ms 3564 KB Output is correct
4 Correct 294 ms 3436 KB Output is correct
5 Correct 254 ms 3436 KB Output is correct
6 Correct 638 ms 3436 KB Output is correct
7 Correct 636 ms 3692 KB Output is correct
8 Correct 406 ms 3180 KB Output is correct
9 Correct 48 ms 1900 KB Output is correct
10 Correct 408 ms 3124 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 5 ms 492 KB Output is correct
12 Correct 9 ms 492 KB Output is correct
13 Correct 8 ms 620 KB Output is correct
14 Correct 11 ms 620 KB Output is correct
15 Correct 11 ms 620 KB Output is correct
16 Correct 8 ms 620 KB Output is correct
17 Correct 6 ms 492 KB Output is correct
18 Correct 7 ms 492 KB Output is correct
19 Correct 877 ms 6164 KB Output is correct
20 Correct 873 ms 5356 KB Output is correct
21 Correct 2102 ms 7100 KB Output is correct
22 Correct 2080 ms 7404 KB Output is correct
23 Correct 2080 ms 7576 KB Output is correct
24 Correct 2430 ms 7296 KB Output is correct
25 Correct 2512 ms 7428 KB Output is correct
26 Correct 1911 ms 7548 KB Output is correct
27 Correct 1914 ms 7588 KB Output is correct
28 Correct 1626 ms 7404 KB Output is correct
29 Correct 831 ms 7276 KB Output is correct
30 Correct 816 ms 7344 KB Output is correct
31 Correct 979 ms 7532 KB Output is correct
32 Correct 885 ms 7280 KB Output is correct
33 Correct 894 ms 7380 KB Output is correct
34 Correct 2377 ms 7404 KB Output is correct
35 Correct 2549 ms 7628 KB Output is correct
36 Correct 2533 ms 7592 KB Output is correct
37 Correct 2504 ms 7660 KB Output is correct
38 Correct 2536 ms 7408 KB Output is correct
39 Correct 1674 ms 7028 KB Output is correct
40 Correct 1012 ms 5448 KB Output is correct
41 Correct 1529 ms 6124 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 5 ms 492 KB Output is correct
12 Correct 9 ms 492 KB Output is correct
13 Correct 8 ms 620 KB Output is correct
14 Correct 11 ms 620 KB Output is correct
15 Correct 11 ms 620 KB Output is correct
16 Correct 8 ms 620 KB Output is correct
17 Correct 6 ms 492 KB Output is correct
18 Correct 7 ms 492 KB Output is correct
19 Runtime error 779 ms 20588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -