Submission #1181926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181926		sofija6	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	831 ms	86440 KiB

sortbooks

#include <bits/stdc++.h>
#define ll long long
#define MAXN 1000010
using namespace std;
ll n,w[MAXN],sz;
vector<pair<ll,pair<ll,ll> > > queries[MAXN];
bool ans[MAXN];
struct seg_tree
{
    vector<ll> st;
    void Init()
    {
        sz=1;
        while (sz<n)
            sz <<= 1;
        st.resize(2*sz+2);
    }
    void Update(ll pos,ll val,ll x,ll lx,ll rx)
    {
        if (lx==rx)
        {
            st[x]=max(st[x],val);
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Update(pos,val,2*x,lx,mid);
        else
            Update(pos,val,2*x+1,mid+1,rx);
        st[x]=max(st[2*x],st[2*x+1]);
    }
    ll Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return 0;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return max(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll m,l,r,k;
    cin >> n >> m;
    for (ll i=1;i<=n;i++)
        cin >> w[i];
    for (ll i=1;i<=m;i++)
    {
        cin >> l >> r >> k;
        queries[r].push_back({l,{k,i}});
    }
    S.Init();
    stack<ll> s;
    for (ll i=1;i<=n;i++)
    {
        while (!s.empty() && w[s.top()]<=w[i])
            s.pop();
        if (!s.empty())
            S.Update(s.top(),w[s.top()]+w[i],1,1,sz);
        s.push(i);
        for (auto p : queries[i])
            ans[p.second.second]=(S.Calc(p.first,i,1,1,sz)<=p.second.first);
    }
    for (ll i=1;i<=m;i++)
        cout << ans[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