Submission #1093239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093239		ivaziva	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	2773 ms	140040 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<int,pair<int,int>>> queries[MAXN];
vector<int> lasts[MAXN];
int seg[MAXN*4];
int ans[MAXN];

void build(int node,int l,int r)
{
    if (l==r)
    {
        if (last[l]==-1) seg[node]=w[l];
        else seg[node]=w[l]+w[last[l]];
    }
    else
    {
        int mid=(l+r)/2;
        build(2*node,l,mid);build(2*node+1,mid+1,r);
        seg[node]=max(seg[2*node],seg[2*node+1]);
    }
}

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});
        if (last[i]!=-1) lasts[last[i]].push_back(i);
    }
    for (int i=0;i<m;i++)
    {
        int l,r,k;cin>>l>>r>>k;
        queries[l].push_back({r,{k,i}});
    }
    for (int i=1;i<=n;i++) sort(queries[i].begin(),queries[i].end());
    build(1,1,n);
    for (int levo=1;levo<=n;levo++)
    {
        for (int p:lasts[levo-1]) update(1,1,n,p,0);
        for (int siz=0;siz<queries[levo].size();siz++)
        {
            int desno=queries[levo][siz].first;
            int val=queries[levo][siz].second.first;
            int poz=queries[levo][siz].second.second;
            if (query(1,1,n,levo,desno)<=val) ans[poz]=1;
            else ans[poz]=0;
        }
    }
    for (int i=0;i<m;i++) cout<<ans[i]<<endl;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int siz=0;siz<queries[levo].size();siz++)
      |                        ~~~^~~~~~~~~~~~~~~~~~~~~

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