Submission #344381

#	Time	Username	Problem	Language	Result	Execution time	Memory
344381		koketsu	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	2549 ms	20588 KiB

sortbooks

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23