oj.uz

Submission #206819

# Submission time Handle Problem Language Result Execution time Memory
206819 2020-03-05T13:46:47 Z mat_v Divide and conquer (IZhO14_divide) C++14
0 / 100
 291 ms 8428 KB 
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define mid(l, r) ((l)+(r))/2
#define len(a) (a).length()
#define sz(a) (a).size()
#define xx first
#define yy second
#define inf int(2e9)
#define ff(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define maxn 100005

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

template<class T>
void print(const T niz[], const int siz)
{
    for(int i=0;i<siz;i++)
        cout << niz[i] << " ";
    cout << endl;
}

int n;
ll x[maxn], d[maxn], g[maxn];
vector<pii> v;
ll res;

pii seg[4 * maxn];
void update(int node, int l, int r, int poz, ll val){
    if(l == r){
        seg[node] = {val, l};
        return;
    }
    int mid = (l + r) / 2;
    if(poz <= mid)update(node * 2, l, mid, poz, val);
    else update(node * 2 + 1, mid + 1, r, poz, val);
    seg[node] = min(seg[node * 2], seg[node * 2 + 1]);
}
pii query(int node, int l, int r, int levo, int desno){
    if(r < levo || l > desno)return {1e15, 0};
    if(l >= levo && r <= desno)return seg[node];
    int mid = (l + r) / 2;
    pii p1 = query(node * 2, l, mid, levo, desno);
    pii p2 = query(node * 2 + 1, mid + 1, r, levo, desno);
    if(p1.xx < p2.xx)return p1;
    else return p2;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    v.pb({0,0});
    ff(i,0,n - 1){
        cin >> x[i] >> g[i] >> d[i];
        res = max(res, g[i]);
        if(i)d[i] += d[i - 1];
        if(i)g[i] += g[i - 1];
        v.pb({d[i] - x[i], g[i]});
    }
    int m = v.size() - 1;
    update(1,0,n,0,0);
    ff(i,1,m){
        ll kolko = v[i].xx;
        int l = 0;
        int r = (i-1);
        if(query(1,0,n,l,r).xx > kolko){
            update(1,0,n,kolko,i);
            continue;
        }
        while(l < r){
            int mid = (l + r) / 2;
            ll pom = query(1,0,n,0,mid).xx;
            if(pom <= kolko)r = mid;
            else l = mid + 1;
        }
        int koji = query(1,0,n,0,l).yy;
        res = max(res, v[i].yy - v[koji].yy);
        if(koji)res = max(res, v[i].yy - v[koji-1].yy);
        update(1,0,n,kolko,i);
    }
    cout << res << endl;
    return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 892 KB Output is correct
2 Correct 25 ms 1276 KB Output is correct
3 Correct 24 ms 1144 KB Output is correct
4 Correct 141 ms 3564 KB Output is correct
5 Correct 137 ms 3824 KB Output is correct
6 Correct 291 ms 7404 KB Output is correct
7 Correct 277 ms 6380 KB Output is correct
8 Correct 284 ms 6252 KB Output is correct
9 Correct 290 ms 8428 KB Output is correct
10 Incorrect 71 ms 5992 KB Output isn't correct
11 Halted 0 ms 0 KB -