oj.uz

Submission #102589

# Submission time Handle Problem Language Result Execution time Memory
102589 2019-03-26T03:36:36 Z AbduM Divide and conquer (IZhO14_divide) C++14
100 / 100
 191 ms 13568 KB 
/// In the name of GOD
/// I love my MOTHER
/// Only GOLD

#include <bits/stdc++.h>

#define all(x)                  x.begin(), x.end()
#define sz(s)                   (ll)(s.size())
#define pb                      push_back
#define pf                      push_front
#define ppb                     pop_back()
#define ppf                     pop_front()
#define F                       first
#define S                       second
#define MP                      make_pair
#define ort1                    exit(0);
#define nl                      "\n"

#define rep(i, l, r)            for(int i = (l); i <= (r); ++i)
#define per(i, l, r)            for(int i = (l); i >= (r); i--)
#define TL                      clock() / (double)CLOCKS_PER_SEC
#define NFS                     ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

const double pi = acos(-1.0);
const double eps = 1e-7;
const long long INF = 1e18 + 1;
const long long inf = 1e12 + 788;
const int mod = 1e9 + 7;
const int N = 1e5 + 7;

int n;
ll x[N], g[N], d[N];
ll a[N], b[N];
vector<ll> v;
map<ll, int> m;

int main(){
    #ifdef ioi
        freopen("in.txt", "r", stdin);
    #endif // ioi

    cin >> n;
    rep(i, 1, n){
        cin >> x[i] >> g[i] >> d[i];
        g[i] += g[i - 1];
        d[i] += d[i - 1];
        a[i] = d[i] - x[i];
        b[i] = d[i - 1] - x[i];
    }

    ll ans = -mod;
    for(int i = 1; i <= n; ++i){
        if(!v.size()) {
            v.pb(b[i]);
            m[b[i]] = i;
        }

        else if(b[i] < v.back()){
            v.pb(b[i]);
            m[b[i]] = i;
        }

        int l = 0, r = v.size() - 1;
        while(l <= r){
            int md = ((l + 1) + (r + 1)) / 2;
            if(v[md - 1] > a[i]) l = (md - 1) + 1;
            else if(v[md - 1] <= a[i]) r = (md - 1) - 1;
        }
        ans = max(ans, g[i] - g[m[v[r + 1]] - 1]);
    }

    cout << ans;

    #ifdef ioi
        cout << nl << TL << nl;
    #endif // ioi

    ort1
}

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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 460 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 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 8 ms 1024 KB Output is correct
12 Correct 9 ms 1024 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 19 ms 896 KB Output is correct
4 Correct 51 ms 3300 KB Output is correct
5 Correct 101 ms 3676 KB Output is correct
6 Correct 130 ms 7272 KB Output is correct
7 Correct 93 ms 6136 KB Output is correct
8 Correct 114 ms 6136 KB Output is correct
9 Correct 101 ms 6008 KB Output is correct
10 Correct 140 ms 9560 KB Output is correct
11 Correct 174 ms 13568 KB Output is correct
12 Correct 191 ms 13456 KB Output is correct