Submission #256593

#	Time	Username	Problem	Language	Result	Execution time	Memory
256593		uacoder123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1694 ms	64760 KiB

sortbooks

    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
  
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int segt[4000001];
int n,m,ans[1000001];
int arr[1000001],pg[1000001];
vector<iii> que[1000001];
void up(int node,int l,int r,int in,int v)
{
  if(l==r)
  {
    segt[node]=v;
    return;
  }
  int mi=(l+r)/2;
  if(in<=mi)
    up(2*node+1,l,mi,in,v);
  else
    up(2*node+2,mi+1,r,in,v);
  segt[node]=max(segt[2*node+1],segt[2*node+2]);
}
int qu(int node,int l,int r,int s,int e)
{
  if(r<s||l>e)
    return(0);
  if(l>=s&&r<=e)
    return(segt[node]);
  int mi=(l+r)/2;
  int q1=qu(2*node+1,l,mi,s,e),q2=qu(2*node+2,mi+1,r,s,e);
  return(max(q1,q2));
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>m;
  stack<int> s;
  for(int i=0;i<n;++i)
    pg[i]=-1;
  for(int i=0;i<n;++i)
  {
    cin>>arr[i];
    while(s.size())
    {
      if(arr[s.top()]<arr[i])
        s.pop();
      else
        break;
    }
    if(s.size())
      pg[i]=s.top();
    s.push(i);
  }
  for(int i=0;i<m;++i)
  {
    int f,sec,k;
    cin>>f>>sec>>k;
    f--;
    sec--;
    que[sec].pb(mp(i,mp(f,k)));
  }
  for(int i=0;i<n;++i)
  {
    if(pg[i]!=-1)
      up(0,0,n-1,pg[i],arr[pg[i]]+arr[i]);
    for(int j=0;j<que[i].size();++j)
      if(qu(0,0,n-1,que[i][j].S.F,i)<=que[i][j].S.S)
        ans[que[i][j].F]=1;
  }
  for(int i=0;i<m;++i)
    cout<<ans[i]<<'\n';
  return(0);
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<que[i].size();++j)
                 ~^~~~~~~~~~~~~~

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