Submission #1288588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288588		kubinsgk8	Art Exhibition (JOI18_art)	C++20	100 / 100	467 ms	24672 KiB

art

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+2;

pair<long long, long long> a[N];

int n;

long long node[N*4], lazy[N*4];

void update_lazy(int goc, int l, int r)
{
    node[goc]+=lazy[goc];

    if(l!=r)
    {
        lazy[goc*2]+=lazy[goc];
        lazy[goc*2+1]+=lazy[goc];
    }

    lazy[goc]=0;
}

void update_pos(int goc, int l, int r, int pos, long long value)
{
    update_lazy(goc, l, r);
    if(pos<l or pos>r)return ;

    if(l==r)
    {
        node[goc]+=value;
        return;
    }


    int mid=(l+r)>>1;

    update_pos(goc*2, l, mid, pos, value);
    update_pos(goc*2+1, mid+1, r, pos, value);

    node[goc]=max(node[goc*2], node[goc*2+1]);

}


void update(int goc, int l, int r, int trai, int phai, long long value)
{
    update_lazy(goc, l, r);

    if(l>phai or r<trai)return;

    if(trai<=l and r<=phai)
    {
        lazy[goc]+=value;
        update_lazy(goc, l, r);
        return;
    }


    int mid=(l+r)>>1;

    update(goc*2, l, mid, trai, phai, value);
    update(goc*2+1, mid+1, r, trai, phai, value);

    node[goc]=max(node[goc*2], node[goc*2+1]);
}

long long get(int goc, int l, int r, int trai, int phai)
{
    update_lazy(goc, l, r);
    if(l>phai or r<trai)return -1e15;

    if(trai<=l and r<=phai)return node[goc];

    int mid=(l+r)>>1;

    return max(get(goc*2, l, mid, trai, phai), get(goc*2+1, mid+1, r, trai, phai));
}




int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n;

    for(int i=1; i<=n; i++)cin>>a[i].first>>a[i].second;


    sort(a+1, a+n+1);

    long long ans=LLONG_MIN;

    for(int i=1; i<=n; i++)
    {
        update_pos(1, 1, n, i, a[i].first);

        update(1, 1, n, 1, i, a[i].second);

        ans=max(ans, get(1, 1, n, 1, i)-a[i].first);
    }

    cout<<ans;

    return 0;
}

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