Submission #1284942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284942		dobri_oke	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	260 ms	327680 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define int long long

const int N = 1e6+100;
int n, m, a[N], dp[5100][5100], t[N * 4], t2[N * 4];
void build(int v, int l, int r){
    if(l == r){
        t[v] = a[l];
        t2[v] = 0;
        return;
    }
    int m = (l + r) / 2;
    build(v + v, l, m);
    build(v + v + 1, m + 1, r);
    t[v] = max(t[v + v], t[v + v + 1]);
    t2[v] = max({t2[v + v], t2[v + v + 1], t[v + v] + t[v + v + 1]});
}
int comb(int v, int u){
    return max({t2[v], t2[u], t[v] + t[u]});
}
int get(int v, int l, int r, int ll, int rr){
    if(l <= ll && r <= rr) return v;
    if(l > rr || ll > r) return 0;
    int m = (l + r) / 2;
    return comb(get(v + v, l, m, ll, rr), get(v + v + 1, m + 1, r, ll, rr));
}
void sub(){
    for(int i = 1; i <= n; i++){
        int mx = a[i];
        for(int j = i + 1; j <= n; j++){
            dp[i][j] = max(dp[i][j], mx + a[j]);
            mx = max(mx, a[j]);
        }
        mx = a[i];
        for(int j = i - 1; j >= 1; j--){
            dp[i][j] = max(dp[i][j], mx + a[j]);
            mx = max(mx, a[j]);
        }
    }
    while(m--){
        int l, r, k;
        cin >> l >> r >> k;
        if(dp[l][r] <= k) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n <= 5000 && m <= 5000){
        sub();
        return;
    }
    build(1, 1, n);
    while(m--){
        int l, r, k;
        cin >> l >> r >> k;
        if(l == r){
            cout << 1 << '\n';
            return;
        }
        if(get(1, 1, n, l, r) <= k) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}

signed main(){   
    ios_base::sync_with_stdio(0);   cin.tie(0);
    //freopen("promote.in","r",stdin);
    //freopen("promote.out","w",stdout);
    int tt=1;
   // cin >> tt;
    while(tt--){
        solve();
    }
}

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