Submission #1166398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166398		omar1312	Divide and conquer (IZhO14_divide)	C++20	100 / 100	22 ms	8436 KiB

divide

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod = 1000000007;
const int N = 200005;
ll a[N+2], dp[N+2], x[N+2], g[N+2], d[N+2], sufd[N+2], sufg[N+2];
struct Segtree{
    vector<array<ll, 2>> t;
    ll off = 1;
    Segtree(int n){
        while(off < n)off <<= 1;
        t.resize(2 * off);
        // t[i] =  - sufd[i] + sufd[query + 1] + a[query] - a[i];
        // query adds a[query] - sufd[query + 1];
        for(int i = 0; i < n; i++){
            t[i + off] = {-x[i] - sufd[i], i};
        }
        for(int i = off - 1; i >= 0; i--){
            t[i] = min(t[i * 2], t[i * 2 + 1]);
        }
    }
    ll query(ll n, ll ql, ll qh, ll nl, ll nh, ll val){
        if(nl > qh || ql > nh){
            return -1;
        }
        if(nl == nh){
            return t[n][1];
        }
        ll m = (nl + nh) / 2;
        if(t[n * 2][0] + val <= 0){
            return query(n * 2, ql, qh, nl, m, val);
        }
        else if(t[n * 2 + 1][0] + val <= 0){
            return query(n * 2 + 1, ql, qh, m + 1, nh, val);
        }
        else{
            return -1;
        }
    }
};
void solve(){
    // dp[i] = go back + a[i]
    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>x[i]>>g[i]>>d[i];
    }
    for(int i = n - 1; i >= 0; i--){
        sufd[i] = sufd[i + 1] + d[i];
        sufg[i] = sufg[i + 1] + g[i];
    }
    Segtree segtree(n);
    ll ans = 0;
    // cout<<segtree.t[3 + segtree.off][0]<<' ';
    for(int i = 0; i < n; i++){
        ll qans = segtree.query(1, 0, i, 0, segtree.off - 1, x[i] + sufd[i + 1]);
        assert(qans != -1);
        // if(qans == -1){
        //     cout<<i<<'\n';
        // }
        ans = max(ans, sufg[qans] - sufg[i + 1]);
    }
    cout<<ans;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    //cin>>tt;
    // freopen("divide.in", "r", stdin);
    // freopen("divide.out", "w", stdout);
    while(tt--){
        solve();
        cout<<'\n';
    }
}

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