Submission #424054

#	Time	Username	Problem	Language	Result	Execution time	Memory
424054		doowey	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2052 ms	97592 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 10;

int val[N * 4 + 512];
int X[N];

void update(int node, int cl, int cr, int id, int v){
    if(cl == cr){
        val[node] = max(val[node], v);
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        update(node * 2, cl, mid, id, v);
    else
        update(node * 2 + 1, mid + 1, cr, id, v);
    val[node]=max(val[node*2],val[node*2+1]);
}

int get(int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr) return 0;
    if(cl >= tl && cr <= tr){
        return val[node];
    }
    int mid = (cl + cr) / 2;
    return max(get(node * 2, cl, mid, tl, tr),get(node*2+1, mid + 1, cr, tl, tr));
}

vector<pii> Q[N];
int idx[N];
bool res[N];

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ){
        cin >> X[i];
    }

    int li, ri;
    int lq;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> li >> ri >> lq;
        idx[iq] = lq;
        Q[li].push_back(mp(ri, iq));
    }
    vector<int> ids;

    for(int i = n; i >= 1; i -- ){

        while(!ids.empty() && X[i] > X[ids.back()]){
            update(1, 1, n, ids.back(), X[i] + X[ids.back()]);
            ids.pop_back();
        }
        ids.push_back(i);

        for(auto x : Q[i]){
            res[x.se] = (get(1, 1, n, i, x.fi) <= idx[x.se]);
        }
    }
    for(int iq = 1; iq <= q; iq ++ ){
        cout << res[iq] << "\n";
    }
    return 0;
}

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