Submission #233498

#	Time	Username	Problem	Language	Result	Execution time	Memory
233498		nicolaalexandra	Art Exhibition (JOI18_art)	C++14	100 / 100	907 ms	33188 KiB

art

#include <bits/stdc++.h>
#define DIM 500010
#define INF 2000000000000000000LL
using namespace std;
struct idk{
    long long a,b;
} v[DIM];

long long aint[DIM*4],sp[DIM],sol;
int n,i;

inline int cmp (idk a, idk b){
    return a.a < b.a;
}

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = sp[st] - v[st].a;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

long long query (int nod, int st, int dr, int x, int y){

    if (x <= st && dr <= y)
        return aint[nod];

    int mid = (st+dr)>>1;
    long long sol_st = -INF, sol_dr = -INF;

    if (x <= mid)
        sol_st = query (nod<<1,st,mid,x,y);
    if (y > mid)
        sol_dr = query ((nod<<1)|1,mid+1,dr,x,y);

    return max (sol_st,sol_dr);

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    sol = -INF;
    for (i=1;i<=n;i++){
        cin>>v[i].a>>v[i].b;
        sol = max (sol,v[i].b);
    }

    sort (v+1,v+n+1,cmp);

    for (i=1;i<=n;i++)
        sp[i] = sp[i-1] + v[i].b;

    build (1,1,n);

    for (i=1;i<n;i++)
        sol = max (sol,v[i].a - sp[i-1] + query(1,1,n,i+1,n));

    cout<<sol;

    return 0;
}

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