Submission #708402

#	Time	Username	Problem	Language	Result	Execution time	Memory
708402		starplat	Art Exhibition (JOI18_art)	C++14	100 / 100	596 ms	32972 KiB

art

#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';
}

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