Submission #206843

#	Time	Username	Problem	Language	Result	Execution time	Memory
206843		mat_v	Divide and conquer (IZhO14_divide)	C++14	100 / 100	306 ms	15316 KiB

divide

#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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52