Submission #1113239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113239		0pt1mus23	Divide and conquer (IZhO14_divide)	C++14	100 / 100	29 ms	10064 KiB

divide

// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 2e5 +23, inf = LLONG_MAX, LG = 20;

int T[sze*4];
int pref[sze];
int gold[sze];
int pos[sze];

void build(int node,int l,int r){
    if(l==r){
        T[node]=pref[l-1]-pos[l];
        return;
    }
    int mid = (l+r)/2;
    build(2*node,l,mid);
    build(2*node +1,mid+1,r);
    T[node]=min(T[node*2],T[node *2 +1]);
}
int qry(int node,int l,int r,int lazim){
    if(l==r){
        return (T[node]<=lazim ? l:0);
    }
    int mid = (l+r)/2;
    if(T[2*node] <= lazim){
        return qry(2*node,l,mid,lazim);
    }
    return qry(2*node +1,mid+1,r,lazim);
}

void fast(){
    int n;
    cin>>n;
    vector<array<int,3>> arr(n+1);
    for(int i=1;i<=n;i++){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
        pos[i]=arr[i][0];
        pref[i]=pref[i-1]+arr[i][2];
        gold[i]=gold[i-1]+arr[i][1];
    }
    build(1,1,n);
    int ans=0;
    for(int i=1;i<=n;i++){
        int r=  qry(1,1,n,pref[i]-arr[i][0]);
        if(r){
            ans=max(ans, gold[i]-gold[r-1]);
        }
    }
    putr(ans);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

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