Submission #1093251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093251		ivaziva	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	77 / 100	3074 ms	72600 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000001

int n,m;
int w[MAXN];
int last[MAXN];
stack<pair<int,int>> st;
vector<pair<pair<int,int>,pair<int,int>>> queries;
int seg[MAXN*4];
int ans[MAXN];

void update(int node,int l,int r,int pos,int val)
{
    if (l==r) seg[node]=val;
    else
    {
        int mid=(l+r)/2;
        if (pos<=mid) update(2*node,l,mid,pos,val);
        else update(2*node+1,mid+1,r,pos,val);
        seg[node]=max(seg[2*node],seg[2*node+1]);
    }
}

int query(int node,int l,int r,int a,int b)
{
    if (a>b) return -INT_MAX;
    if (l==a and r==b) return seg[node];
    int mid=(l+r)/2;
    return max(query(2*node,l,mid,a,min(b,mid)),query(2*node+1,mid+1,r,max(a,mid+1),b));
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>w[i];
    for (int i=1;i<=n;i++)
    {
        while (st.size()!=0 and st.top().first<=w[i]) st.pop();
        if (st.size()==0) last[i]=-1;
        else last[i]=st.top().second;
        st.push({w[i],i});
    }
    for (int i=0;i<m;i++)
    {
        int l,r,k;cin>>l>>r>>k;
        queries.push_back({{r,l},{k,i}});
    }
    sort(queries.begin(),queries.end());
    int trenr=0;
    for (int i=0;i<m;i++)
    {
        while (trenr<queries[i].first.first)
        {
            trenr++;
            if (last[trenr]==-1) continue;
            update(1,1,n,last[trenr],w[trenr]+w[last[trenr]]);
        }
        int sol=query(1,1,n,queries[i].first.second,queries[i].first.first);
        if (sol<=queries[i].second.first) ans[queries[i].second.second]=1;
        else ans[queries[i].second.second]=0;
    }
    for (int i=0;i<m;i++) cout<<ans[i]<<endl;
}

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