Submission #204494

#	Time	Username	Problem	Language	Result	Execution time	Memory
204494		T0p_	Art Exhibition (JOI18_art)	C++14	100 / 100	318 ms	53820 KiB

art

#include<bits/stdc++.h>
using namespace std;

struct data
{
	long long a, b;	
	bool operator < (const data & o) const
	{
		return a < o.a;	
	}
};

struct tree
{
	long long s, sl, sr, ans;	
};

data arr[500500];
tree seg[2002000];

void build(int l, int r, int idx)
{
	if(l == r)
	{
		seg[idx] = {arr[l].b, arr[l].b - arr[l].a, arr[l].b + arr[l].a, arr[l].b};
		return ;
	}
	int mid = (l+r)>>1;
	build(l, mid, idx<<1);
	build(mid+1, r, idx<<1|1);
	long long S = seg[idx<<1].s + seg[idx<<1|1].s;
	long long SL = max(seg[idx<<1].sl, seg[idx<<1].s + seg[idx<<1|1].sl);
	long long SR = max(seg[idx<<1|1].sr, seg[idx<<1|1].s + seg[idx<<1].sr);
	long long ANS = max(max(seg[idx<<1].ans, seg[idx<<1|1].ans), seg[idx<<1].sr + seg[idx<<1|1].sl);
	seg[idx] = {S, SL, SR, ANS};
}

int main()
{
	int n;
	scanf(" %d",&n);
	for(int i=1 ; i<=n ; i++)
		scanf(" %lld %lld",&arr[i].a, &arr[i].b);
	sort(arr+1, arr+n+1);
	build(1, n, 1);
	printf("%lld\n",seg[1].ans);
	return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d",&n);
  ~~~~~^~~~~~~~~~
art.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %lld %lld",&arr[i].a, &arr[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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