제출 #540388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540388		andrei_boaca	Art Exhibition (JOI18_art)	C++17	100 / 100	899 ms	37336 KiB

art

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct date
{
    ll a,b;
} v[500005];
ll ans=0;
int n;
bool comp(date a, date b)
{
    return a.a<b.a;
}
ll arb[2000005],toprop[2000005];
void prop(int nod)
{
    ll val=toprop[nod];
    for(int i=nod*2;i<=nod*2+1;i++)
    {
        arb[i]+=val;
        toprop[i]+=val;
    }
}
void update(int nod,int st,int dr,int a,int b,ll val)
{
    if(st!=dr)
        prop(nod);
    toprop[nod]=0;
    if(st>=a&&dr<=b)
    {
        arb[nod]+=val;
        toprop[nod]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);
    arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
ll query(int nod,int st,int dr,int a,int b)
{
    if(st!=dr)
        prop(nod);
    toprop[nod]=0;
    if(st>=a&&dr<=b)
        return arb[nod];
    int mij=(st+dr)/2;
    ll rez=0;
    if(a<=mij)
        rez=max(rez,query(nod*2,st,mij,a,b));
    if(b>mij)
        rez=max(rez,query(nod*2+1,mij+1,dr,a,b));
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].a>>v[i].b;
    sort(v+1,v+n+1,comp);
    for(int i=1;i<=n;i++)
    {
        update(1,1,n,i,n,v[i].b);
        update(1,1,n,i,i,-v[i].a);
    }
    for(int i=1;i<=n;i++)
    {
        update(1,1,n,i,n,+v[i].a);
        ll val=query(1,1,n,i,n);
        ans=max(ans,val);
        update(1,1,n,i,n,-v[i].a);
        update(1,1,n,i,n,-v[i].b);
        update(1,1,n,i,i,+v[i].a);
    }
    cout<<ans;
    return 0;
}

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