Submission #733878

#	Time	Username	Problem	Language	Result	Execution time	Memory
733878		bgnbvnbv	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2019 ms	141432 KiB

sortbooks

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,q;
struct IT
{
    ll st[4*maxN];
    void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
    {
        if(l==r)
        {
            st[id]=val;
            return;
        }
        ll mid=l+r>>1;
        if(pos<=mid) update(pos,val,id*2,l,mid);
        else update(pos,val,id*2+1,mid+1,r);
        st[id]=max(st[id*2],st[id*2+1]);
    }
    ll get(ll i,ll j,ll id=1,ll l=1,ll r=n)
    {
        if(i>j||j<l||r<i) return -inf;
        if(i<=l&&r<=j) return st[id];
        ll mid=l+r>>1;
        return max(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
    }
}it1,it2;
ll a[maxN],k[maxN],ans[maxN];
vector<pli>hoi[maxN];
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=q;i++)
    {
        ll l,r;
        cin >> l >> r>> k[i];
        hoi[r].pb({l,i});
    }
    deque<int>dq;
    for(int i=1;i<=n;i++) it1.update(i,a[i]),it2.update(i,-inf);
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty()&&a[i]>=a[dq.back()])
        {
            ll id=dq.back();
            it2.update(id,it1.get(id+1,i-1)+a[id]);
            dq.pop_back();
        }
        for(auto zz:hoi[i])
        {
            ans[zz.se]=it2.get(zz.fi,i);
            ll cc=lower_bound(dq.begin(),dq.end(),zz.fi)-dq.begin();
            if(cc<dq.size())
            {
                ans[zz.se]=max(ans[zz.se],a[dq[cc]]+it1.get(dq[cc]+1,i));
            }
        }
        dq.push_back(i);
    }
    for(int i=1;i<=q;i++)
    {
        //cout << ans[i]<<'\n';
        if(k[i]>=ans[i]) cout << 1<<'\n';
        else cout << 0<<'\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void IT::update(ll, ll, ll, ll, ll)':
sortbooks.cpp:24:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         ll mid=l+r>>1;
      |                ~^~
sortbooks.cpp: In member function 'll IT::get(ll, ll, ll, ll, ll)':
sortbooks.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         ll mid=l+r>>1;
      |                ~^~
sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:63:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if(cc<dq.size())
      |                ~~^~~~~~~~~~

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