#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
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;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
