Submission #868504

#	Time	Username	Problem	Language	Result	Execution time	Memory
868504		hqminhuwu	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	672 ms	90716 KiB

sortbooks

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 1e6 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int bit[N],n;
void update (int u, int val){
    for (; u > 0; u -= u & -u)
        bit[u] = max (bit[u],val);
}

int get (int u){
    int res = 0;
    for (; u <= n; u += u & -u)
        res = max (res,bit[u]);
    return res;
}

stack <int> s;
int q,i,a[N],u,v,h[N],ans[N];
vector <pii> g[N];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    forr (i,1,n)
        cin >> a[i];
    forr (i,1,q){
        cin >> u >> v;
        cin >> h[i];
        g[v].pb({i,u});
    }
    
    forr (i,1,n){
        while (!s.empty() && a[i] >= a[s.top()])
            s.pop();
        if (!s.empty())
            update(s.top(),a[i] + a[s.top()]);
        s.push(i);
        for (pii w : g[i])
            ans[w.st] = get(w.nd);
    }
    forr (i,1,q)
        cout << (ans[i] <= h[i]) << "\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