oj.uz

Submission #951314

# Submission time Handle Problem Language Result Execution time Memory
951314 2024-03-21T15:23:45 Z LOLOLO Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 6492 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 100;
ll seg[N * 4], dp[N];
int n;

void point(int id, int l, int r, int p, ll v) {
    if (l > p || r < p)
        return;

    seg[id] = min(seg[id], v);
    if (l == r)
        return;

    int m = (l + r) / 2;
    point(id * 2, l, m, p, v);
    point(id * 2 + 1, m + 1, r, p, v);
}

ll get(int id, int l, int r, int u, int v) {
    if (l > v || r < u)
        return 1e18;

    if (l >= u && r <= v)
        return seg[id];

    int m = (l + r) / 2;
    return min(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}

ll x[N], g[N], d[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;

    fill(seg, seg + n * 4 + 10, 1e18);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> g[i] >> d[i];
        g[i] += g[i - 1];
        d[i] += d[i - 1];
    }

    map <ll, int> mp;
    int timer = 1;
    for (int i = 1; i <= n; i++) {
        mp[x[i] - d[i - 1]];
        mp[x[i] - d[i]];
    }

    for (auto &x : mp) {
        x.s = timer;
        timer++;
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int p = mp[x[i] - d[i]];
        ans = max({ans, g[i] - get(1, 1, n, p, n), g[i] - g[i - 1]});
        point(1, 1, n, mp[x[i] - d[i - 1]], g[i - 1]);
    }

    cout << ans << '\n';
    return 0;
}

/*
en[i] = g[1] + g[2] +..+ g[i];
s[i] =  d[1] + d[2] +..+ d[i];
dp[i] = tổng lớn nhất.
dp[i] = max(dp[i - 1], dp[j - 1] + en[i] - en[j - 1]); 
(x[i] - x[j] <= s[i] - s[j - 1])
<=> x[i] - s[i] <= x[j] - s[j - 1]
*/

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -