Submission #1155297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155297		imarn	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	619 ms	67232 KiB

sortbooks

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=1e6+5;
int w[mxn],l[mxn],r[mxn],ans[mxn];
vector<t3>qr[mxn];
int t[2*mxn]{0};
void upd(int i,int sz,int amt){
    i+=sz;t[i]=max(t[i],amt);
    for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
}
int query(int l,int r,int sz,int rs=0){
    for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
        if(l&1)rs=max(rs,t[l++]);
        if(r&1)rs=max(rs,t[--r]);
    }return rs;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    stack<int>st;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&w[i]>=w[st.top()])st.pop();
        if(!st.empty())l[i]=st.top();
        else l[i]=0;st.push(i);
    }
    for(int i=1;i<=m;i++){
        int l,r,k;cin>>l>>r>>k;
        qr[r].pb({l,i,k});
    }
    for(int i=1;i<=n;i++){
        if(l[i]!=0)upd(l[i]-1,n,w[i]+w[l[i]]);
        for(auto [l,id,k] : qr[i]){
            ans[id]=(query(l-1,i,n)<=k);
        }
    }for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}

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