oj.uz

Submission #206843

# Submission time Handle Problem Language Result Execution time Memory
206843 2020-03-05T14:15:45 Z mat_v Divide and conquer (IZhO14_divide) C++14
100 / 100
 306 ms 15316 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;
}
vector<pii> v2;

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    //v.pb({0,0});
    v2.pb({0,0});
    ff(i,0,n - 1){
        cin >> x[i] >> g[i] >> d[i];
        res = max(res, g[i]);
        if(i)v2.pb({d[i - 1] - x[i], g[i - 1]});
        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,0,4 * (n + 1))seg[i] = {1e15,0};

    ff(i,0,m){
        ll kolko = v[i].xx;
        ll stadodajem = v2[i].xx;
       // cout << stadodajem << "     ";
        int l = 0;
        int r = (i);
        //cout << i << " " << query(1,0,n,l,r).xx << endl;
        if(query(1,0,n,l,r).xx > kolko){
            update(1,0,n,i,stadodajem);
            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;
        }
        //cout << i << " " << l << endl;
        int koji = query(1,0,n,0,l).yy;
        res = max(res, v[i].yy - v2[koji].yy);
        //if(koji)res = max(res, v[i].yy - v[koji-1].yy);
        update(1,0,n,i,stadodajem);
    }
    cout << res << endl;
    return 0;
}
/*
3
1 1 1
1000 2 2
1002 2 1
*/

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 7 ms 636 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 8 ms 1144 KB Output is correct
12 Correct 8 ms 1144 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1144 KB Output is correct
2 Correct 24 ms 1908 KB Output is correct
3 Correct 25 ms 1908 KB Output is correct
4 Correct 133 ms 7516 KB Output is correct
5 Correct 134 ms 7780 KB Output is correct
6 Correct 306 ms 15316 KB Output is correct
7 Correct 289 ms 14168 KB Output is correct
8 Correct 287 ms 14036 KB Output is correct
9 Correct 278 ms 13904 KB Output is correct
10 Correct 227 ms 14040 KB Output is correct
11 Correct 80 ms 14424 KB Output is correct
12 Correct 114 ms 14548 KB Output is correct