제출 #1346004

#제출 시각아이디문제언어결과실행 시간메모리
1346004nagorn_phDivide and conquer (IZhO14_divide)C++20
100 / 100
33 ms8392 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
const int N = 2e5 + 5;

int fenwick[N];
void update(int idx, int val){while (idx < N) fenwick[idx] = min(fenwick[idx], val), idx += idx & -idx;}
int query(int idx){int mx = inf; while (idx > 0) mx = min(mx, fenwick[idx]), idx -= idx & -idx; return mx;}

void solve(){
    int n; cin >> n;
    vector <int> x(n + 1), g(n + 1), d(n + 1);
    vector <int> prefx(n + 1), prefg(n + 1), prefd(n + 1);
    vector <int> val(n + 1);
    vector <int> compress;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> g[i] >> d[i];
        prefx[i] = x[i];
        prefg[i] = prefg[i - 1] + g[i];
        prefd[i] = prefd[i - 1] + d[i];
        val[i] = prefd[i] - prefx[i];
        compress.emb(val[i]);
    }
    compress.emb(0);
    for (int i = 1; i < N; i++) fenwick[i] = inf;
    sort(all(compress));
    int ans = *max_element(all(g));
    compress.erase(unique(all(compress)), compress.end());
    for (int i = 1; i <= n; i++) {
        int idx = lower_bound(all(compress), prefd[i - 1] - x[i]) - compress.begin() + 1;
        update(idx, prefg[i - 1]);
        idx = lower_bound(all(compress), val[i]) - compress.begin() + 1;
        ans = max(ans, prefg[i] - query(idx));
    }
    cout << ans;
}

int32_t main(){
    iShowSpeed;
    // int q; cin >> q; while (q--) 
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...