Submission #87269

#	Time	Username	Problem	Language	Result	Execution time	Memory
87269		Yaroslaff	Divide and conquer (IZhO14_divide)	C++14	100 / 100	271 ms	54856 KiB

divide

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
#define int ll
#define ld long double
#define null nullptr
#define endl '\n'
//13092003

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int M = 1e9 + 7;
const int N = 1e6 + 7;

struct segtree{
    int tn = 1;
    vector<int> t;

    segtree(int n){
        while (tn < n) tn <<= 1;
        t.resize(tn<<1|1, M*M);
    }

    void upd(int p, int x){
        if (t[p + tn] < x) return;
        for (t[p += tn] = x; p > 1; p >>= 1)
            t[p>>1] = min(t[p], t[p^1]);
    }

    int q(int v, int tl, int tr, int l, int r){
        if (r <= tl || tr <= l) return M*M;
        if (l <= tl && tr <= r) return t[v];
        int m = (tl + tr)>>1;
        return min(q(v<<1, tl, m, l, r), q(v<<1|1, m, tr, l, r));
    }

    int q(int l, int r){
        return q(1, 0, tn, l, r);
    }
};

int n, x[N], a[N], b[N], K, res = -1;
unordered_map<int,int> mp;
set<int> all;
segtree t(N);

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#else
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
#endif
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> x[i] >> a[i] >> b[i], a[i] += (i ? a[i - 1] : 0);
    int z = 0;
    for (int i = 0; i < n; i++){
        int d = (i ? x[i] - x[i - 1] : x[i]);
        z += d - b[i];
        all.insert(z);
        all.insert(z + b[i]);
    }
    for (auto it : all) mp[it] = K++;
    z = 0;
    for (int i = 0; i < n; i++){
        int d = (i ? x[i] - x[i - 1] : x[i]);
        z += d - b[i];
        t.upd(mp[z + b[i]], (i ? a[i - 1] : 0));
        res = max(res, a[i] - t.q(mp[z], K + 1));
    }
    cout << res;
    return 0;
}

Compilation message (stderr)

divide.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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