Submission #741999

#	Time	Username	Problem	Language	Result	Execution time	Memory
741999		BidoTeima	Divide and conquer (IZhO14_divide)	C++17	0 / 100	1 ms	980 KiB

divide

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <string>
#include <random>
#include <chrono>
#include <memory.h>
using namespace std;
using ll = long long;
map<ll, int>idx{};
const int N = 1e5 + 3;
ll a[N];
ll st[4 * N];
void build(int l, int r, int node){
    if(l == r){
        st[node] = 1e18;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, 2 * node + 1);
    build(mid + 1, r, 2 * node + 2);
    st[node] = 1e18;
}
ll query(int ql, int qr, int l, int r, int node){
    if(r < ql || l > qr)
        return 1e18;
    if(ql <= l && r <= qr)
        return st[node];
    int mid = (l + r) >> 1;
    return min(query(ql, qr, l, mid, 2 * node + 1), query(ql, qr, mid + 1, r, 2 * node + 2));
}
void update(int idx, int l, int r, int node){
    if(idx<l||idx>r)
        return;
    if(l == r){
        st[node] = a[idx];
        return;
    }
    int mid = (l + r) >> 1;
    update(idx, l, mid, 2 * node + 1);
    update(idx, mid + 1, r, 2 * node + 2);
    st[node] = min(st[2 * node + 1], st[2 * node + 2]);
}
int main()
{         
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int n;
    cin>>n;
    set<pair<ll, ll>>st;
    vector<vector<ll>>arr;
    vector<ll> sorted; 
    ll pref = 0;
    for(int i = 0; i < n; i++){
        ll x,g,d;
        cin>>x>>g>>d;
        arr.push_back({x, g, d});
        sorted.push_back(x - pref);
        pref += d;
    } 
    sort(sorted.begin(), sorted.end());
    for(int i = 0; i < n; i++){
        idx[sorted[i]] = i;
    }
    build(0, n - 1, 0);
    fill(a, a + N, 1e18);
    ll gold = 0, energy = 0, ans = 0;
    for(int i = 0; i < n; i++){
        ll x = arr[i][0], g = arr[i][1], d = arr[i][2];
        int ref = idx[x - energy];
        a[ref] = min(a[ref], gold);
        update(ref, 0, n - 1, 0);
        gold += g, energy += d;
        ans = max(ans, gold - query(ref, n - 1, 0, n - 1, 0));
    }
    cout<<ans<<'\n';
    return 0;
}

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