Submission #359860

#	Time	Username	Problem	Language	Result	Execution time	Memory
359860		shahriarkhan	Divide and conquer (IZhO14_divide)	C++14	100 / 100	73 ms	9948 KiB

divide

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

struct tree
{
    vector<int> t ;
    tree(int a[] , int n)
    {
        t = vector<int> (4*n + 4 , 0) ;
        build(a,1,1,n) ;
    }
    void build(int a[] , int node , int low , int high)
    {
        if(low==high) t[node] = a[low] ;
        else
        {
            int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
            build(a,left,low,mid) , build(a,right,mid+1,high) ;
            t[node] = max(t[left],t[right]) ;
        }
    }
    int query(int node ,int low , int high , int l , int r)
    {
        if(l>high || r<low) return 0 ;
        if(l<=low && high<=r) return t[node] ;
        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 bs(int n , long long val , long long pref[] , long long ind[] , int a[])
{
    int low = 1 , high = n ;
    while(low<high)
    {
        int mid = (low+high)>>1 ;
        if((pref[a[mid]]-ind[a[mid]])>=val) high = mid ;
        else low = mid + 1 ;
    }
    return low ;
}

int main()
{
    int n ;
    scanf("%d",&n) ;
    long long pref[n+1] = {0} , ind[n+1] = {0} , gold[n+1] = {0} , pref_g[n+1] = {0} , ans = 0 ;
    int a[n+1] ;
    vector<pair<long long , int> > v ;
    for(int i = 1 ; i <= n ; ++i)
    {
        long long x , g , d ;
        scanf("%lld%lld%lld",&x,&g,&d) ;
        pref[i] = pref[i-1] + d ;
        pref_g[i] = pref_g[i-1] + g ;
        ind[i] = x , gold[i] = g ;
        v.push_back({pref[i] - ind[i],i}) ;
    }
    sort(v.begin(),v.end()) ;
    for(int i = 1 ; i <= n ; ++i) a[i] = v[i-1].second ;
    tree T(a,n) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        int pos = bs(n,pref[i-1] - ind[i],pref,ind,a) ;
        ans = max(ans,pref_g[T.query(1,1,n,pos,n)] - pref_g[i-1]) ;
    }
    printf("%lld\n",ans) ;
    return 0 ;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
divide.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%lld%lld%lld",&x,&g,&d) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52