제출 #247446

#제출 시각아이디문제언어결과실행 시간메모리
247446sckmdArt Exhibition (JOI18_art)C++14
100 / 100
901 ms58404 KiB
#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;
}

컴파일 시 표준 에러 (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;
          ~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...