Submission #1109973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109973		whyalwaysmezzz	Art Exhibition (JOI18_art)	C++14	0 / 100	1 ms	2384 KiB

art

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define BIT(mask,i) ((mask >> i) & 1ll )
#define endl '\n'  
#define all(x) x.begin(),x.end()
#define ii pair <int,int> 
using namespace std;
#define read doc() 
int doc () {bool minus = false;int result = 0;char ch;ch = getchar();while (true) {if (ch == '-') break;if (ch >= '0' && ch <= '9') break;ch = getchar();}if (ch == '-') minus = true; else result = ch-'0';while (true) {ch = getchar();if (ch < '0' || ch > '9') break;result = result*10 + (ch - '0');}if (minus)return -result;else return result;}
template<class X, class Y>bool minimize(X &x, const Y &y) {if (x > y) {x = y;return true;} else return false;}
template<class X, class Y>bool maximize(X &x, const Y &y) {if (x < y) {x = y;return true;} else return false;}
const long long oo = 1e18;
const int N = 1e6+5;
const int MOD = 1e9+7;
ii a[N];
int f[N];
int st[N*4];
void update(int id,int l,int r,int i,int val)
{
	if ( l > i || r < i) return;
	if (l == r && r == i)
	{
		st[id] = val;
		return;
	}
	int m = l + r >> 1;
	update(id*2,l,m,i,val);
	update(id*2+1,m+1,r,i,val);
	st[id] = min(st[id*2] , st[id*2+1]);
}
int get(int id,int l,int r,int u,int v)
{
	if ( l > v || r < u) return oo;
	if ( l >= u && r <= v ) return st[id];
	int m = l + r >> 1;
	return min(get(id*2,l,m,u,v) , get(id*2+1,m+1,r,u,v));
}
void Whyalwaysmezzz()
{
	int n;
	cin >> n;
	// FOR(i,1,n) cin >> a[i];
	FOR(i,1,n)
	{
		cin >> a[i].fi >> a[i].se;
	}
	sort(a+1,a+1+n);
	FOR(i,1,n) f[i] = f[i-1] + a[i].se;
	FOR(i,1,n) update(1,0,n,i,oo);
	int ans = 0;
	FOR(i,1,n)
	{
		int x = get(1,0,n,0,i-1);
		ans = max(ans,f[i] - a[i].fi - x);
		update(1,0,n,i,f[i-1]  - a[i].fi);
	}
	cout << ans;
    return;
}
#define TASK "task"
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);//freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);
    int Sty1e = 1;
    // cin >> Sty1e;
    while (Sty1e--) Whyalwaysmezzz();
    return 0;       
}

Compilation message (stderr)

art.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
art.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int m = l + r >> 1;
      |          ~~^~~
art.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
art.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int m = l + r >> 1;
      |          ~~^~~

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