제출 #1350449

#제출 시각아이디문제언어결과실행 시간메모리
1350449bbbirosArt Exhibition (JOI18_art)C++20
0 / 100
0 ms344 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define X first
#define Y second
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int n;
const int MAXN = 500100;
pair<ll, ll> a[MAXN];
ll mx = 0;
void read()
{
    mx = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].X >> a[i].Y;
        mx = max(mx, a[i].Y);
    }
    sort(a + 1, a + 1 + n);
}
ll tree[MAXN*4];
ll lazy[MAXN*4];
void push_lazy(int node,int l,int r)
{
    if(lazy[node]>0)
    {
        tree[node]+=lazy[node];
        if(l!=r)
        {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
}
void update(int node,int l,int r,int ql,int qr,ll qv)
{
    push_lazy(node,l,r);
    if(l>=ql &&r<=qr)
    {
        lazy[node]+=qv;
        push_lazy(node,l,r);
        return;
    }
    if(l>qr||r<ql)return;
    int mid=(l+r)/2;
    update(node*2,l,mid,ql,qr,qv);
    update(node*2+1,mid+1,r,ql,qr,qv);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}
void solve()
{
    update(1,1,n,1,1,a[1].Y);
    for(int i=2;i<=n;i++)
    {
        update(1,1,n,1,i-1,a[i].Y-(a[i].X-a[i-1].X));
        update(1,1,n,i,i,a[i].Y);
        mx=max(mx,tree[1]);
    }
}
signed main()
{
    speed();
    read();
    solve();
    cout << mx << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...