Submission #362746

#	Time	Username	Problem	Language	Result	Execution time	Memory
362746		bigDuck	Divide and conquer (IZhO14_divide)	C++14	100 / 100	94 ms	22380 KiB

divide

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int n;
int x[100010], g[100010], d[100010];


int sum[100010];
int a[100010];
int e[100010];


int rmq[100010][21];
int lg2[100010];

void RMQ(){
    for(int i=0; i<=n;i++){
        rmq[i][0]=a[i];
    }
    for(int j=1; j<=20; j++){
        for(int i=0; (i+(1ll<<j)-1)<=n; i++){
            rmq[i][j]=min(rmq[i][j-1], rmq[i+(1ll<<(j-1) )][j-1]);
        }
    }

    int lg=0;
    for(int i=1; i<=n; i++){
        if(i>=(1<<(lg+1))){
            lg++;
        }
        lg2[i]=lg;
    }

}


int query(int l, int r){
    int lg=lg2[r-l+1];
    return min(rmq[l][lg], rmq[r-(1ll<<lg)+1][lg]);
}


int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n;i++){
    cin>>x[i]>>g[i]>>d[i];
    sum[i]=sum[i-1]+g[i];
    e[i]=e[i-1]+d[i];
}

for(int i=0; i<n; i++){
    a[i]=e[i]-(x[i+1]-1);
}
a[0]=0;
RMQ();

int res=0;
for(int i=1; i<=n; i++){
    int l=0, r=i-1, m=(l+r)>>1ll;
    while(l<r){
        m=(l+r)>>1ll;
        if(query(0, m)<=(e[i]-x[i]) ){
            r=m;
        }
        else{
            l=(m+1);
        }
        m=(l+r)>>1ll;
    }

    res=max(res, sum[i]-sum[m]);

}
cout<<res;



return 0;
}

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