Submission #502914

#	Time	Username	Problem	Language	Result	Execution time	Memory
502914		nickmet2004	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	100 / 100	2966 ms	99388 KiB

sortbooks

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
int n , q , a[N] , d[N] , ans[N];
int T[4*N];
void upd(int id , int d , int l = 1 , int r =n , int pos =1){
    if(id < l || id > r)return;
    if(l==r){
        T[pos] = d;return;
    }
    int mid = (l + r) >> 1;
    upd(id , d ,l , mid , pos * 2); upd(id ,d , mid + 1 , r ,pos * 2 + 1);
    T[pos] = max(T[pos * 2] , T[pos * 2 + 1]);
}
int get(int L ,int R , int l = 1 ,int r = n , int pos = 1){
    if(r < L || R < l)return 0;
    if(L <= l && r <= R)return T[pos];
    int mid = (l + r) >> 1;
    return max(get(L , R , l , mid , pos *2) , get(L , R , mid + 1 , r , pos * 2 + 1));
}
vector<pair<int , int> > Q[N];
 main (){
    ios_base::sync_with_stdio(0);
    cin >> n>>q;
    vector<int> K;
    for(int i = 1; i<= n; ++i)cin >> a[i];
    for(int i = 0; i < q; ++i){
        int l , r;
        cin >> l >> r>>d[i];
        Q[r].emplace_back(l , i);
    }
    stack<int> s;
    for(int R = 1; R <= n; ++R){
        while(s.size() && a[s.top()] <= a[R])s.pop();
        if(s.size()) upd(s.top() , a[R] + a[s.top()]);
        s.push(R);
        for(auto x : Q[R]){
            if(get(x.first , R) <= d[x.second])ans[x.second] = 1;
            else ans[x.second] = 0;
        }
    }
    for(int i = 0; i <q; ++i)cout << ans[i] <<endl;
    //for(int x : T[9].s)cout << x << "x ";

}

Compilation message (stderr)

sortbooks.cpp:23:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 |  main (){
      |  ^~~~

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