Submission #1285015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285015		alizhan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2660 ms	110932 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod =  1e9 + 7;
const int N = (int)1e6 + 7;
#define skip continue
#define uno first
#define duo second
#define GO while(tt--)
#define ins insert
#define pb push_back
#define all(x) x.begin(), x.end()
#define Kaldun ios::sync_with_stdio(false); cin.tie(nullptr)
#define int long long

int bp(int a, int n) {
    if(n == 0) return 1;
    if(n % 2 == 1) return (bp(a, n-1) * a) % mod;
    long long b = bp(a, n/2);
    return (b * b) % mod;
}int f[1001];
int sz[N*4],t[N*4];
vector<array<int , 3>>q[N+1];
void push(int v){
    if(sz[v]){
        t[v*2] += sz[v];
        t[v*2+1] += sz[v];
        sz[v*2] += sz[v];
        sz[v*2+1] += sz[v];
        sz[v] = 0;
    }
}
void upd(int v,int tl,int tr,int l,int r,int x){
    if (tl > r || tr < l) return;
    if (l <= tl && tr <= r) {
        t[v] += x;
        sz[v] += x;
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    upd(v + v, tl, tm, l, r, x);
    upd(v + v + 1, tm+1, tr, l, r, x);
    t[v] = max(t[v + v], t[v + v + 1]);
}
int get(int v,int tl,int tr,int l,int r){
    if(tl > r || tr < l) return 0;
    if(l<=tl && tr<=r) return t[v];
    push(v);
    int tm = (tl + tr)/2;
    return max(get(v*2,tl,tm,l,r) , get(v*2+1,tm+1,tr,l,r));
}
int comb(int n, int k){if(k < 0 || k > n) return 0;int d = (f[k] * 1LL * f[n - k]) % mod;return (f[n] * 1LL * bp(d, mod - 2)) % mod;}
int lcm(int a,int b){ return (a * b) / __gcd(a,b);}
void solve(){
    int n,m;
    cin>>n>>m;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        int l,r,k;
        cin>>l>>r>>k;
        q[l].push_back({r,k,i});
    }
    for(int i=1;i<=n;i++) upd(1,1,n,i,i,a[i]);
    stack<int>s;
    int res[m+1]{};
    for(int i=n;i>=1;i--){
        while(!s.empty() && a[i] > a[s.top()]){
            int u = s.top();
            s.pop();
            int l;
            if(s.empty()) l = n;
            else l = s.top() - 1;
            upd(1,1,n,u,u,a[u]);
            upd(1,1,n,u+1,l,-a[u]);
        }
        int l;
        if(s.empty()) l =n;
        else l = s.top() - 1;
        upd(1,1,n,i,i,-a[i]);
        upd(1,1,n,i+1,l,a[i]);
        s.push(i);
        for (auto [r, k, id] : q[i]) {
            if (get(1, 1, n, i, r) <= k) res[id] = 1;
            else res[id] = 0;
        }
    }
    for(int i=1;i<=m;i++){
        cout<<res[i]<<endl;
    }
}
signed main() {
    Kaldun;
    cout.precision(0);
    //freopen("time.in", "r", stdin);
    //freopen("time.out", "w", stdout);
    int tt=1;
    //cin>>tt;
    while(tt--){
        solve();
    }
}

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