Submission #1353045

#TimeUsernameProblemLanguageResultExecution timeMemory
1353045eraliArt Exhibition (JOI18_art)C++20
100 / 100
522 ms55596 KiB
#include<bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 

#define sz() size()
#define all(v) (v).begin(),(v).end() 
#define F first
#define S second
#define pb push_back
#define popb pop_back
#define ss sort
#define rr reverse 
#define pii pair <int, int>
#define pll pair <ll, ll>
 
using namespace std;
using ld = long double;
using ll = long long;

const int N = 5e5+10;
const ll inf = 1e18;
const int Mod = 1e9+7;
const int P = 273;

int n;
ll a[N], b[N], t[N*4], pref[N];
vector <ll> vec;

void build(int v = 1, int tl = 1, int tr = n) 
{
	if (tl == tr) 
	{
		t[v] = pref[tl] - vec[tl-1];
		return;
	}
	
	int tm = tl + tr >> 1;
	build(v + v, tl, tm);
	build(v + v + 1, tm + 1, tr);
	
	t[v] = max(t[v + v], t[v + v + 1]);
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n) 
{
	if (tl > r || tr < l) return -inf;
	if (l <= tl && tr <= r)  return t[v];
	int tm = tl + tr >> 1;
	return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

void Erali_is_the_best(int testCase) 
{	
	cin >> n;
	
	map <ll, ll> mp;
	for (int i = 1; i <= n; ++i) 
	{
		cin >> a[i] >> b[i];
		if (!mp.count(a[i])) vec.pb(a[i]);
		mp[a[i]] += b[i];
	}
	
	ss(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	
	n = vec.sz();
	for (int i = 1; i <= n; ++i) 
	{
		pref[i] = pref[i-1] + mp[vec[i-1]];
	}
	
	build();
	
	ll ans = 0, sum = 0;
	for (int i = 1; i <= n; ++i) 
	{
		ll val = get(i, n) - sum;
		
		ans = max(vec[i-1] + val, ans);
		sum += mp[vec[i-1]];
		
		// cout << ans << " ";
	}
	
	cout << ans << "\n";
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	// freopen("cardgame.in","r",stdin);
  	// freopen("cardgame.out","w",stdout);
  	int tt = 1;
	// cin >> tt; 
	for (int test = 1; test <= tt; ++test)
	{
		Erali_is_the_best(test);
	}
}
 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...