Submission #945267

#	Time	Username	Problem	Language	Result	Execution time	Memory
945267		fzyzzz_z	Divide and conquer (IZhO14_divide)	C++17	100 / 100	113 ms	27332 KiB

divide

#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

const ll inf = 1e18 + 50;

struct Z {
    ll x, y, v; 
    Z() {}
};

ll t[262144 * 2];  
void upd(int x, ll v, int L = 0, int R = 262144 - 1, int at = 1) {
    if (x < L || x > R) return; 
    t[at] = min(t[at], v); 
    if (L == R) return; 
    int mid = (L + R) / 2; 
    upd(x, v, L, mid, at * 2); 
    upd(x, v, mid + 1, R, at * 2 + 1); 
}

ll query(int l, int r, int L = 0, int R = 262144 - 1, int at = 1) {
    if (l > R || L > r) return (1LL << 60); 
    if (l <= L && R <= r) {
        return t[at]; 
    }
    int mid = (L + R) / 2; 
    ll x = query(l, r, L, mid, at * 2); 
    ll y = query(l, r, mid + 1, R, at * 2 + 1); 
    return min(x, y); 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < 262144 * 2; ++i) t[i] = (1LL << 60); 

    int n; 
    cin >> n; 
    vector<Z> a(n); 
    vector<pair<ll, ll>> xs;
    vector<ll> gx(n), ex(n); 

    ll e = 0, g = 0; 
    for (int i = 0; i < n; ++i) {
        ll x, y, z; 
        cin >> x >> y >> z; 

        gx[i] = y; 
        ex[i] = z; 

        a[i].x = x; 
        a[i].y = e; 
        a[i].v = g;

        xs.push_back({e - x, i}); 
        xs.push_back({e + z - x, i}); 

        g += y; 
        e += z;
    }
    sort(xs.begin(), xs.end()); 
    map<pair<ll, ll>, int> to; 
    for (int i = 0; i < 2 * n; ++i) {
        // cout << xs[i].first << ' ' << xs[i].second << '\n';
        to[xs[i]] = i; 
    }
    ll ans = 0; 
    for (int i = 0; i < n; ++i) {
        int c = to[make_pair(a[i].y - a[i].x, i)]; 
        upd(c, a[i].v); 
        // cout << "updating " << c << ' ' << a[i].v << '\n';

        c = to[make_pair(a[i].y + ex[i] - a[i].x, i)]; 
        ans = max(ans, a[i].v + gx[i] - query(0, c)); 

        // cout << "! proc " << i << '\n';
        // cout << c << ' ' << query(0, c) << '\n';
        // cout << a[i].v + gx[i] - query(0, c) << '\n';
    }

    cout << ans << '\n';

    return 0;
}

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