Submission #708402

#TimeUsernameProblemLanguageResultExecution timeMemory
708402starplatArt Exhibition (JOI18_art)C++14
100 / 100
596 ms32972 KiB
#include <bits/stdc++.h>
#define int long long
#define mid (x+y)/2
using namespace std;
int n,ans,par[500005];
pair<int,int> a[500005];
int t[500005<<2];
void build(int id,int x,int y)
{
	if (x==y) t[id]=a[x].first-par[x-1];
	else {
		build(id*2,x,mid);
		build(id*2+1,mid+1,y);
		t[id]=max(t[id*2],t[id*2+1]);
	}
}
int query(int id,int x,int y,int l,int r)
{
	if (x>r || y<l) return 0;
	if (l<=x && y<=r) return t[id];
	return max(query(id*2,x,mid,l,r),query(id*2+1,mid+1,y,l,r));
}
signed main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) par[i]=par[i-1]+a[i].second;
	build(1,1,n);
	for (int i=1;i<=n;i++){
		ans=max(ans,par[i]-a[i].first+query(1,1,n,1,i));
	}
	cout<<ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...