Submission #247446

#	Time	Username	Problem	Language	Result	Execution time	Memory
247446		sckmd	Art Exhibition (JOI18_art)	C++14	100 / 100	901 ms	58404 KiB

art

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct st{
	ll a,b;
};

#define MAXN 500005
const ll INF = 1e18;
st all[MAXN];
map <ll,int> mp;
int hsh = 0;

bool cmp(st x,st y)
{
	return x.a < y.a;
}

ll tree[4*MAXN];
ll lazy[4*MAXN];

void push(int node,int left,int right)
{
	if(lazy[node]!=0)
	{
		tree[node] += lazy[node];
		if(left != right)
		{
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int node,int left,int right,int l,int r,ll val)
{
	push(node,left,right);
	if(left > right || left > r || l > right)return ;
	if(left >= l && right <= r)
	{
		lazy[node]+=val;
		push(node,left,right);
		return ;
	}
	int mid = left+right>>1;
	update(node*2,left,mid,l,r,val);
	update(node*2+1,mid+1,right,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}
ll query(int node,int left,int right,int l,int r)
{
	push(node,left,right);
	if(left > right || left > r || l > right)return -INF;
	if(left >= l && right <= r)return tree[node];
	int mid = left+right>>1;
	return max(query(node*2,left,mid,l,r),query(node*2+1,mid+1,right,l,r));
}
void build(int node,int left,int right)
{
	if(left == right)
	{
		tree[node]=-INF;
		return ;
	}
	int mid=left+right>>1;
	build(node*2,left,mid);
	build(node*2+1,mid+1,right);
	tree[node]=-INF;
}

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		ll a,b;
		cin >> a >> b;
		st ss;
		ss.a=a;ss.b=b;
		all[i]=ss;
	}
	sort(all,all+n,cmp);
	build(1,1,n);
	ll ans = -INF;
	for(int i = 0; i < n; i++)
	{
		ll a = all[i].a;
		ll b = all[i].b;
		if(!mp[a])mp[a]=++hsh;
		int code = mp[a];
		if(query(1,1,n,code,code) == -INF)update(1,1,n,code,code,INF+a);
		update(1,1,n,1,code,b);
		ans = max(ans,query(1,1,n,1,n)-a);
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

art.cpp: In function 'void update(int, int, int, int, int, ll)':
art.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = left+right>>1;
            ~~~~^~~~~~
art.cpp: In function 'll query(int, int, int, int, int)':
art.cpp:58:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = left+right>>1;
            ~~~~^~~~~~
art.cpp: In function 'void build(int, int, int)':
art.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=left+right>>1;
          ~~~~^~~~~~

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