Submission #1176231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176231		emil_aliyevv	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2100 ms	113808 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxpq = priority_queue<T, vector<T>, less<T>>;

void input(vll&q)
{
    for(auto&i:q)cin>>i;
}
void pyn(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
void pYN(bool x)
{
    cout<<(x?"Yes":"No")<<endl;
}
void pAB(bool x)
{
    cout<<(x?"Alice":"Bob")<<endl;
}
const ll N=1e6+10;
vector<vll> query[N];
ll fen[N],ans[N];
ll n,m;
void update(ll ind,ll val)
{
    ind++;
    while(ind>0)
    {
        fen[ind]=max(fen[ind],val);
        ind-=(ind&-ind);
    }
}
ll get(ll i)
{
    i++;
    ll ans=0;
    while(i<=n)
    {
        ans=max(ans,fen[i]);
        i+=(i&-i);
    }
    return ans;
}
void solve()
{
    cin>>n>>m;
    vll a(n);
    input(a);
    vll bp;
    for(int i=0;i<m;i++)
    {
        ll l,r,k;
        cin>>l>>r>>k;
        l--;
        r--;
        query[r].push_back({l,k,i});
    }
    for(ll l=0;l<n;l++)
    {
        while(bp.size()>0 and a[bp.back()]<=a[l])
        {
            bp.pop_back();
        }
        if(bp.size())
        {
            update(bp.back(),a[bp.back()]+a[l]);
        }
        for(auto lp:query[l])
        {
            ans[lp[2]]=(get(lp[0])<=lp[1]);
        }
        bp.push_back(l);
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<endl;
}

int main()
{
    int t=1;
    // cin>>t;
    while(t--)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