oj.uz

Submission #175805

# Submission time Handle Problem Language Result Execution time Memory
175805 2020-01-07T11:17:34 Z _Enkognit Divide and conquer (IZhO14_divide) C++14
100 / 100
 341 ms 11384 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pll pair<ll,ll>
#define y1 Enkognit
#define fi first
#define se second
#define pld pair<ld,ld>

using namespace std;

const ll MOD=1000000007;

ll l, r, n, m, k, y, leaf[10000001], a[1000001], x[1000001], b[1000001];
ll tt[10000001];
vector <ll> an;

ll binpow(ll h,ll r)
{
    ll l=1;
    while (r)
    {
        if (r&1) l*=h,l%=MOD;
        h*=h;
        h%=MOD;
        r/=2;
    }
    return l;
}

ll d[10000001];

void push(int h)
{
    if (leaf[h]) return;
    if (tt[h])
    {
        d[h*2]+=tt[h];
        tt[h*2]+=tt[h];
        d[h*2+1]+=tt[h];
        tt[h*2+1]+=tt[h];
        tt[h]=0;
    }
}

void build(int h,int l,int r)
{
    if (l==r) {leaf[h]=1;d[h]=-1;return;}
    int w=(l+r)/2;
    build(h*2,l,w);
    build(h*2+1,w+1,r);
    d[h]=-1;
}

void update(int h,int l,int r,int x,int y,int k)
{
    //cout << l << " " << x << " " << y << " " << r << "\n";
    push(h);
    if (x>y) return;
    if (l==x && y==r)
    {
        d[h]+=k;
        tt[h]+=k;
        push(h);
        return;
    }
    int w=(l+r)/2;
    update(h*2,l,w,x,min(y,w),k);
    update(h*2+1,w+1,r,max(x,w+1),y,k);
    d[h]=max(d[h*2],d[h*2+1]);
}

ll get(int h,int l,int r)
{
    push(h);
    if (l==r) return l;
    int w=(l+r)/2;
    if (d[h*2]>=0) return get(h*2,l,w); else return get(h*2+1,w+1,r);
}

int main()
{
    //ios::sync_with_stdio(0);
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
        cin >> x[i] >> b[i] >> a[i];
        b[i]+=b[i-1];
    }
    ll ans=0;
    build(1,1,n);
    for (int i = 1; i <= n; i++)
    {
        update(1,1,n,i,i,1);
        //cout << i << "\n";
        update(1,1,n,1,i,a[i]);
        update(1,1,n,1,i-1,x[i-1]-x[i]);
        ans=max(ans,b[i]-b[get(1,1,n)-1]);
    }
    cout << ans;
    return 0;
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1
*/

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 4 ms 424 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 15 ms 916 KB Output is correct
12 Correct 16 ms 888 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 888 KB Output is correct
2 Correct 23 ms 1400 KB Output is correct
3 Correct 27 ms 1528 KB Output is correct
4 Correct 142 ms 5404 KB Output is correct
5 Correct 157 ms 5820 KB Output is correct
6 Correct 341 ms 11384 KB Output is correct
7 Correct 269 ms 10104 KB Output is correct
8 Correct 277 ms 10232 KB Output is correct
9 Correct 263 ms 9964 KB Output is correct
10 Correct 264 ms 9976 KB Output is correct
11 Correct 294 ms 10488 KB Output is correct
12 Correct 305 ms 10840 KB Output is correct