제출 #1346586

#제출 시각아이디문제언어결과실행 시간메모리
1346586Born_To_Laugh금 캐기 (IZhO14_divide)C++17
100 / 100
30 ms5940 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e18 + 7;
// prefenergy[i] - x[i] >= prefenergy[j - 1] - x[j]
// ans = max(prefg[i] - prefg[j - 1]);

struct Fen
{
    int n;
    vector<ll> bit;
    void init(int len){
        n = len;
        bit.assign(n + 1, INF);
    }
    void upd(int pos, ll val){
        for(; pos<=n; pos += pos & -pos) bit[pos] = min(bit[pos], val);
    }
    ll qr(int pos){
        ll ans = INF;
        for(; pos>0; pos -= pos & -pos) ans = min(ans, bit[pos]);
        return ans;
    }
};

const int maxn = 1e5 + 10;
int n;
ll x[maxn], prefe[maxn], prefg[maxn];
Fen ft;
vector<ll> temp;

void solve(){
    cin >> n;
    temp.push_back(-INF);
    ll ans = 0;
    for(int i=1; i<=n; ++i){
        cin >> x[i] >> prefg[i] >> prefe[i];
        ans = max(ans, prefg[i]);
        prefg[i] += prefg[i - 1];
        prefe[i] += prefe[i - 1];
        temp.push_back(prefe[i] - x[i]);
        temp.push_back(prefe[i - 1] - x[i]);
    }
    sort(alle(temp));
    temp.erase(unique(alle(temp)), temp.end());
    ft.init(temp.size() + 1);

    auto get_pos = [&](ll num) -> int {
        int id = lower_bound(alle(temp), num) - temp.begin();
        return id;
    };
    for(int i=1; i<=n; ++i){
        ans = max(ans, prefg[i] - ft.qr(get_pos(prefe[i] - x[i])));
        ft.upd(get_pos(prefe[i - 1] - x[i]), prefg[i - 1]);
    }
    cout << ans << '\n';
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...