Submission #997696

#	Time	Username	Problem	Language	Result	Execution time	Memory
997696		I_FloPPed21	Art Exhibition (JOI18_art)	C++14	100 / 100	610 ms	40020 KiB

art

#include <iostream>
#include <algorithm>
using namespace std;
int n;
struct arta
{
    long long x, y;
}v[500005];

long long seg[2000005],lz[2000005];

void update( int nod , int st, int dr, int l ,int r , long long val )
{
    if( l <= st && dr <= r )
    {
        lz[nod] += val ;
        seg[nod] += val ;
    }
    else
        if( l > dr || st > r )
        return ;
    else
    {
        int mij = ( st +dr ) / 2;
        lz[nod*2] += lz[nod],seg[nod*2]+= lz[nod];
        lz[nod*2+1] += lz[nod],seg[nod*2+1] += lz[nod];
        lz[nod] = 0 ;
        update(nod*2,st,mij,l,r,val) ;
        update(nod*2+1,mij+1,dr,l,r,val);
        seg[nod] = max( seg[nod*2],seg[nod*2+1]);
    }
}

long long query(int nod ,int st , int dr ,int l , int r )
{
    if( l <= st && dr <= r )
        return seg[nod];
    else
        if( st > r || dr < l )
        return -1e18;
    else
    {
        int mij = ( st + dr ) / 2;
        lz[nod*2] += lz[nod],lz[nod*2+1]+= lz[nod];
        seg[nod*2] += lz[nod],seg[nod*2+1] += lz[nod];
        lz[nod] = 0 ;
        return max(query(nod*2,st,mij,l,r),query(nod*2+1,mij+1,dr,l,r));
    }
}
bool tdl ( arta x , arta y )
{
    return ( x.x < y.x);
}
int main()
{
    cin >> n ;
    for (int i = 1; i <= n ; i ++ )
        cin >> v[i].x>>v[i].y;
    sort(v+1,v+n+1,tdl);

    long long ans = 0;
    for ( int i = 1 ; i <= n ;i ++ )
    {
        update(1,1,n,1,i,v[i].y);
       if ( i != 1 )
            update(1,1,n,1,i - 1 ,-(v[i].x - v[i-1].x));

            //cout << query(1,1,n,1,1)<< '\n';
        ans = max ( ans , query(1,1,n,1,i));
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50