Submission #1269495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269495		krzyska	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1045 ms	64328 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
int n;
int tab[1000006];

struct zap{
    int l;
    int k;
    int i;
};
vector<zap> Q[1000006];

constexpr int base = (1 << 20);
int drzewo[base*2];

int a, b;
int maximum(int v, int l, int p){
    if(a <= l && p <= b){
        return drzewo[v];
    }
    if(a > p || b < l){
        return 0;
    }

    return max(maximum(v*2, l, (l + p)/2), maximum(v*2 + 1, (l + p)/2 + 1, p));
}

void zmiana(int v, int x){
    v += base;
    drzewo[v] = max(drzewo[v], x);
    v /= 2;

    while(v){
        drzewo[v] = max(drzewo[v*2], drzewo[v*2 + 1]);
        v /= 2;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> tab[i];
    }

    for(int i = 1; i <= q; i++){
        zap xd;
        int r;
        cin >> xd.l >> r >> xd.k;
        xd.i = i;
        Q[r].push_back(xd);
    }

    bool odp[q + 1];
    int wiekszy[n + 1];
    stack<int> sztos;

    for(int i = 1; i <= n; i++){
        while(sztos.size() && tab[sztos.top()] <= tab[i]){
            sztos.pop();
        }
        if(sztos.size()){
            wiekszy[i] = sztos.top();
        }
        else{
            wiekszy[i] = 0;
        }
        sztos.push(i);
    }

    for(int i = 1; i <= n; i++){
        if(wiekszy[i]){
            zmiana(wiekszy[i], tab[i] + tab[wiekszy[i]]);
        }
        for(auto j:Q[i]){
            a = j.l;
            b = i;
            if(maximum(1, 0, base - 1) > j.k){
                odp[j.i] = 0;
            }
            else{
                odp[j.i] = 1;
            }
        }
    }

    for(int i = 1; i <= q; i++){
        cout << odp[i] << '\n';
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23