oj.uz

Submission #168642

# Submission time Handle Problem Language Result Execution time Memory
168642 2019-12-14T18:12:30 Z muhammad_hokimiyon Divide and conquer (IZhO14_divide) C++14
100 / 100
 233 ms 29236 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define ll long long

using namespace std;

const int N = 1e5 + 7;
const int mod = 1e9 + 7;

int n;
ll a[N];
ll b[N];
ll d[N];
ll g[N];
ll t[8 * N];
map < ll , int > m;
vector < pair < ll , pair < ll , ll > > > v;

ll get( int x , int l , int r , int tl , int tr )
{
    if( tl > tr )return 1e18;
    if( l == tl && r == tr ){
        return t[x];
    }
    int mid = (l + r) / 2;
    return min( get( x * 2 , l , mid , tl , min(tr , mid) ) ,
               get( x * 2 + 1 , mid + 1 , r , max(tl , mid + 1) , tr ) );
}

void upd( int x , int l , int r , int pos , ll val )
{
    if( l == r ){
        t[x] = min( t[x] , val );
        return;
    }
    int mid = (l + r) / 2;
    if( mid >= pos )upd( x * 2 , l , mid , pos , val );
    else upd( x * 2 + 1 , mid + 1 , r , pos , val );
    t[x] = min( t[x * 2] , t[x * 2 + 1] );
}

void solve()
{
    cin >> n;
    ll ans = 0;
    for( int i = 1; i <= n; i++ ){
        ll x,y,z;
        cin >> x >> y >> z;
        ans = max( ans , y );
        v.push_back({x , {y , z}});
    }
    for( int i = 1; i <= 8 * n; i++ ){
        t[i] = 1e18;
    }
    sort( v.begin() , v.end() );
    vector < ll > o;
    for( int i = 0; i < (int)v.size(); i++ ){
        d[i] = v[i].se.se;
        if( i > 0 )d[i] += d[i - 1] , g[i] = g[i - 1];
        g[i] += v[i].se.fi;
        a[i] = d[i - 1] - v[i].fi;
        b[i] = d[i] - v[i].fi;
        o.push_back(a[i]);
        o.push_back(b[i]);
    }
    int G = 0;
    sort( o.begin() , o.end() );
    for( int i = 0; i < (int)o.size(); i++ ){
        if( m.find(o[i]) == m.end() ){
            m[o[i]] = ++G;
        }
    }
    for( int i = 0; i < (int)v.size(); i++ ){
        ll x = get( 1 , 1 , G , 1 , m[b[i]] );
        //cout << i << " " << x << " " << m[a[i]] << " " << m[b[i]] << " " << g[i] << "\n";
        ans = max( ans , g[i] - x );
        upd( 1 , 1 , G , m[a[i]] , (i > 0 ? g[i - 1] : 0) );
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int t = 1;//cin >> t;
    while( t-- ){
        solve();
    }
}

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 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 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 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 564 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 4 ms 888 KB Output is correct
11 Correct 9 ms 1720 KB Output is correct
12 Correct 10 ms 1720 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1764 KB Output is correct
2 Correct 18 ms 2932 KB Output is correct
3 Correct 19 ms 2944 KB Output is correct
4 Correct 106 ms 13308 KB Output is correct
5 Correct 110 ms 14536 KB Output is correct
6 Correct 233 ms 29236 KB Output is correct
7 Correct 223 ms 27932 KB Output is correct
8 Correct 223 ms 27976 KB Output is correct
9 Correct 232 ms 27872 KB Output is correct
10 Correct 223 ms 27420 KB Output is correct
11 Correct 230 ms 28368 KB Output is correct
12 Correct 231 ms 28464 KB Output is correct