제출 #226078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226078		dvdg6566	Art Exhibition (JOI18_art)	C++14	100 / 100	456 ms	91348 KiB

art

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 500100;
const ll INF = 1e18;
const ll MOD = 1e9+7;

pi A[MAXN];
vpi V;
ll N,a,b;

struct node{
    ll s,e,m,v,lazy;
    node *l,*r;
    node(int _s,int _e):s(_s), e(_e){
        m=(s+e)/2;v=-V[s].f;lazy=0;
        // cout<<"Original "<<v<<' '<<V[]
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
            v=max(l->v,r->v);
        }
    }
    void up(int x, int y, int val){
        if (s==x&&e==y){lazy+=val;return;}
        if (y<=m)l->up(x,y,val);
        else if (x>m)r->up(x,y,val);
        else {l->up(x,m,val);r->up(m+1,y,val);}
        v=max(l->v+l->lazy, r->v+r->lazy);
    }
    ll query(ll x, ll y){
        if (s==x&&e==y)return v+lazy;
        if (y<=m)return l->query(x,y);
        if (x>m)return r->query(x,y);
        return max(l->query(x,m), r->query(m+1,y));
    }
}*root;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>N;
    for (int i=1;i<=N;++i){
        cin>>A[i].f>>A[i].s;
    }
    sort(A+1,A+N+1);
    for(int i=1;i<=N;++i){
        if (SZ(V) && V.back().f == A[i].f){
            V.back().s += A[i].s;
        }else V.pb(A[i]);
    }
    ll ans = 0;
    N = SZ(V);
    root = new node(0,N-1);
    for (int i=0;i<N;++i){
        // cout<<i<<' '<<V[i].s<<'\n';
        root->up(i,N-1,V[i].s);
    }
    for (int i=0;i<N;++i){
        ll offset = V[i].s+V[i].f;
        // cout<<"At "<<V[i].f<< " offset is "<<offset<<'\n';
        root->up(i,N-1,-V[i].s);
        ll v = root->query(i,N-1);
        // cout<<"Value "<<v<<'\n';
        ans=max(ans,v+offset);
    }
    cout<<ans;
}

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