Submission #256501

#	Time	Username	Problem	Language	Result	Execution time	Memory
256501		uacoder123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3099 ms	241896 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;
    vi segt[4000001];
    int n,m,ans[4000001],ans1;
    int arr[1000001];
    void merge(int node)
    {
      int s=0,s1=0;
      while(s!=segt[2*node+1].size()||s1!=segt[2*node+2].size())
      {
        if(s!=segt[2*node+1].size()&&(s1==segt[2*node+2].size()||segt[2*node+1][s]<=segt[2*node+2][s1]))
        {
          segt[node].pb(segt[2*node+1][s]);
          s++;
        }
        else
        {
          if(s!=segt[2*node+1].size())
            ans[node]=max(ans[node],segt[2*node+2][s1]+(*(--segt[2*node+1].end())));
          segt[node].pb(segt[2*node+2][s1]);
          s1++;
        }
      }
    }
    void build(int node,int l,int r)
    {
      if(l==r)
      {
        ans[node]=0;
        segt[node].pb(arr[l]);
        return;
      }
      ans[node]=max(ans[2*node+1],ans[2*node+2]);
      int m=(l+r)/2;
      build(2*node+1,l,m);
      build(2*node+2,m+1,r);
      merge(node);
    }
    ii qu(int node,int l,int r,int s,int e,int cm)
    {
      if(l>e||r<s)
        return(mp(0,cm));
      if(l>=s&&r<=e)
      {
        int it=lower_bound(all(segt[node]),cm)-segt[node].begin();
        ans1=0;
        if(it!=0)
        {
          it--;
          ans1=cm+segt[node][it];
        }
        return(mp(max(ans[node],ans1),max(cm,(*(--segt[node].end())))));
      }
      int m=(l+r)/2;
      ii q1=qu(2*node+1,l,m,s,e,cm);
      ii q2=qu(2*node+2,m+1,r,s,e,q1.S);
      return(mp(max(q1.F,q2.F),q2.S));
    }
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      cin>>n>>m;
      for(int i=0;i<n;++i)
        cin>>arr[i];
      build(0,0,n-1);
      for(int i=0;i<m;++i)
      {
        int f,s,k;
        cin>>f>>s>>k;
        f--;
        s--;
        ii a=qu(0,0,n-1,f,s,arr[f]);
        if(a.F<=k)
          cout<<1<<'\n';
        else
          cout<<0<<'\n';
      }
      return(0);
    }

Compilation message (stderr)

sortbooks.cpp: In function 'void merge(int)':
sortbooks.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(s!=segt[2*node+1].size()||s1!=segt[2*node+2].size())
             ~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:26:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(s!=segt[2*node+1].size()||s1!=segt[2*node+2].size())
                                       ~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:28:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(s!=segt[2*node+1].size()&&(s1==segt[2*node+2].size()||segt[2*node+1][s]<=segt[2*node+2][s1]))
            ~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:28:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(s!=segt[2*node+1].size()&&(s1==segt[2*node+2].size()||segt[2*node+1][s]<=segt[2*node+2][s1]))
                                       ~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           if(s!=segt[2*node+1].size())
              ~^~~~~~~~~~~~~~~~~~~~~~~

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