oj.uz

Submission #87269

# Submission time Handle Problem Language Result Execution time Memory
87269 2018-11-30T06:37:15 Z Yaroslaff Divide and conquer (IZhO14_divide) C++14
100 / 100
 271 ms 54856 KB 
#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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 15 ms 16768 KB Output is correct
3 Correct 16 ms 16816 KB Output is correct
4 Correct 16 ms 17076 KB Output is correct
5 Correct 15 ms 17076 KB Output is correct
6 Correct 16 ms 17076 KB Output is correct
7 Correct 18 ms 17076 KB Output is correct
8 Correct 16 ms 17096 KB Output is correct
9 Correct 15 ms 17096 KB Output is correct
10 Correct 15 ms 17096 KB Output is correct
11 Correct 15 ms 17096 KB Output is correct
12 Correct 17 ms 17096 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17096 KB Output is correct
2 Correct 17 ms 17184 KB Output is correct
3 Correct 17 ms 17200 KB Output is correct
4 Correct 16 ms 17212 KB Output is correct
5 Correct 17 ms 17356 KB Output is correct
6 Correct 18 ms 17384 KB Output is correct
7 Correct 19 ms 17420 KB Output is correct
8 Correct 17 ms 17440 KB Output is correct
9 Correct 17 ms 17588 KB Output is correct
10 Correct 19 ms 17872 KB Output is correct
11 Correct 25 ms 18424 KB Output is correct
12 Correct 23 ms 18536 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18536 KB Output is correct
2 Correct 28 ms 19748 KB Output is correct
3 Correct 32 ms 19876 KB Output is correct
4 Correct 114 ms 28896 KB Output is correct
5 Correct 133 ms 30184 KB Output is correct
6 Correct 271 ms 42980 KB Output is correct
7 Correct 261 ms 44860 KB Output is correct
8 Correct 254 ms 46844 KB Output is correct
9 Correct 242 ms 48532 KB Output is correct
10 Correct 255 ms 49828 KB Output is correct
11 Correct 261 ms 52448 KB Output is correct
12 Correct 248 ms 54856 KB Output is correct