Submission #68434

#	Time	Username	Problem	Language	Result	Execution time	Memory
68434		yusufake	Divide and conquer (IZhO14_divide)	C++98	100 / 100	88 ms	19820 KiB

divide

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5;

ll F[N+N],X[N],G[N],D[N],T[N+N],t,n,i,j,ans;

ll qry(int x){
    ll t = 1LL << 55;
    for(; x ; x -= x&-x)
        t = min(t , F[x]);
    return t;
}           
                        
void up(int x, ll a){
    for(; x <= t ; x += x&-x)
        F[x] = min(F[x] , a);
}    
        
int main(){         
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld%lld%lld",&X[i],&G[i],&D[i]);
        G[i] += G[i-1];
        D[i] += D[i-1];
        T[++t] = D[i]-X[i];
        T[++t] = D[i-1]-X[i];   
    }                                   
    sort(T+1 , T+t+1);                          
    memset(F , 127 , sizeof F);                         
    for(i=1;i<=n;i++){                                      
        j = lower_bound(T+1 , T+t+1 , D[i-1]-X[i]) - T;
        up(j,G[i-1]);
        j = lower_bound(T+1 , T+t+1 , D[i]-X[i]) - T;
        ans = max(ans , G[i] - qry(j)); 
    }                                       
                                                    
    printf("%lld", ans);                                    
    return 0;                                                   
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
divide.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&X[i],&G[i],&D[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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