Submission #568828

#	Time	Username	Problem	Language	Result	Execution time	Memory
568828		shahriarkhan	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	308 KiB

segments

#include<bits/stdc++.h>
using namespace std ;

#define ll long long

const int MX = 5e5 + 5 ;

const pair<ll,ll> emp = {0,0} ;

pair<ll,ll> dp[MX] ;

struct lazytree
{
    vector<pair<ll,ll> > t , lazy ;
    void init(int n)
    {
        t = vector<pair<ll , ll> > (4*n + 4 , emp) ;
        lazy = vector<pair<ll , ll> > (4*n + 4 , emp) ;
    }
    void upd(int node , pair<ll,ll> val)
    {
        t[node] = max(t[node],val) ;
        lazy[node] = max(lazy[node],val) ;
    }
    void shift(int node , int low , int high)
    {
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        upd(left,lazy[node]) ;
        upd(right,lazy[node]) ;
        lazy[node] = emp ;
    }
    void update(int node , int low , int high , int l , int r , pair<ll,ll> val)
    {
        if(l>r) return ;
        if((r<low) || (l>high)) return ;
        if((l<=low) && (high<=r))
        {
            upd(node,val) ;
            return ;
        }
        shift(node,low,high) ;
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        update(left,low,mid,l,r,val) ;
        update(right,mid+1,high,l,r,val) ;
        t[node] = max(t[left],t[right]) ;
    }
    pair<ll,ll> query(int node , int low , int high , int l , int r)
    {
        if(l>r) return emp ;
        if((r<low) || (l>high)) return emp ;
        if((l<=low) && (high<=r)) return t[node] ;
        shift(node,low,high) ;
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        return max(query(left,low,mid,l,r),query(right,mid+1,high,l,r)) ;
    }
};

int main()
{
    int n ;
    scanf("%d",&n) ;
    ll a[n+2] , pref[n+2] = {0} ;
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%lld",&a[i]) ;
        pref[i] += (pref[i-1]+a[i]) ;
    }
    lazytree T ;
    T.init(n) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        pair<ll,ll> cur = {1,pref[i]} , qc = T.query(1,1,n,i,i) ;
        cur = max(cur,{qc.first,pref[i]-qc.second}) ;
        int low = 0 , high = n ;
        while(low<high)
        {
            int mid = (low+high)>>1 ;
            if((pref[mid]-pref[i])>=cur.second) high = mid ;
            else low = mid + 1 ;
        }
        dp[i] = cur ;
        T.update(1,1,n,low,n,{cur.first+1,pref[i]}) ;
    }
    printf("%lld\n",dp[n].first) ;
    return 0 ;
}

Compilation message (stderr)

segments.cpp: In member function 'void lazytree::shift(int, int, int)':
segments.cpp:27:13: warning: unused variable 'mid' [-Wunused-variable]
   27 |         int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
      |             ^~~
segments.cpp: In function 'int main()':
segments.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
segments.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%lld",&a[i]) ;
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27