oj.uz

Submission #106280

# Submission time Handle Problem Language Result Execution time Memory
106280 2019-04-17T18:47:48 Z Frankenween Divide and conquer (IZhO14_divide) C++17
100 / 100
 228 ms 26988 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 608 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 752 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 568 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 6 ms 1024 KB Output is correct
11 Correct 10 ms 1664 KB Output is correct
12 Correct 9 ms 1664 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1664 KB Output is correct
2 Correct 18 ms 2944 KB Output is correct
3 Correct 21 ms 3020 KB Output is correct
4 Correct 98 ms 13168 KB Output is correct
5 Correct 99 ms 13168 KB Output is correct
6 Correct 228 ms 25380 KB Output is correct
7 Correct 206 ms 25324 KB Output is correct
8 Correct 197 ms 25404 KB Output is correct
9 Correct 199 ms 25424 KB Output is correct
10 Correct 194 ms 24648 KB Output is correct
11 Correct 193 ms 26856 KB Output is correct
12 Correct 188 ms 26988 KB Output is correct