Submission #106280

#	Time	Username	Problem	Language	Result	Execution time	Memory
106280		Frankenween	Divide and conquer (IZhO14_divide)	C++17	100 / 100	228 ms	26988 KiB

divide

#include <bits/stdc++.h>


//#define _FORTIFY_SOURCE 0
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ull unsigned long long
#define pii pair<ll, ll>
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define vi vector<ll>

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = atan2l(0, -1);


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


struct mine {
    ll x, gold, en;
};


struct stree {
    vector<ll> t;

    void upd(ll v, ll l, ll r, ll pos, ll val) {
        if (l == r) {
            t[v] = val;
            return;
        }
        ll mid = (l + r) / 2;
        if (pos <= mid) {
            upd(v * 2, l, mid, pos, val);
        } else {
            upd(v * 2 + 1, mid + 1, r, pos, val);
        }
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }

    ll query(ll v, ll l, ll r, ll ql, ll qr) {
        if (ql <= l and r <= qr) {
            return t[v];
        }
        if (ql > r or qr < l) {
            return inf;
        }
        ll mid = (l + r) / 2;
        return min(query(v * 2, l, mid, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
    }
};


void solve() {
    ll n;
    cin >> n;
    vector<mine> line(n);
    for (int i = 0; i < n; i++) {
        cin >> line[i].x >> line[i].gold >> line[i].en;
    }
    ll esum = 0;
    vector<ll> all_vals;
    for (int i = 0; i < n; i++) {
        all_vals.pb(line[i].x - esum);
        esum += line[i].en;
        all_vals.pb(line[i].x - esum);
    }
    sort(all(all_vals));
    map<ll, ll> cord;
    ll cnt = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (i == 0 or all_vals[i] != all_vals[i - 1]) {
            cord[all_vals[i]] = cnt;
            cnt++;
        }
    }
    stree t;
    t.t.resize(4 * cnt, inf);
    vector<ll> values(cnt, inf);
    ll answer = 0, gold = 0, en = 0;
    for (int i = 0; i < n; i++) {
        if (values[cord[line[i].x - en]] == inf) {
            t.upd(1, 0, cnt - 1, cord[line[i].x - en], gold);
            values[cord[line[i].x - en]] = 0;
        }
        gold += line[i].gold;
        en += line[i].en;
        answer = max(answer, gold - t.query(1, 0, cnt - 1, cord[line[i].x - en], cnt - 1));
    }
    cout << answer;
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    srand(time(0));
    cout.setf(ios::fixed);
    solve();
    return 0;
}

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