#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#include <bits/stdc++.h>
#define ll long long int
#define speed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define TxtIO freopen("lol.in","r",stdin); freopen("lol.txt","w",stdout);
#define forn(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
struct segtree{
vector <ll> tree;
ll size;
void init(ll n){
size=1;
while(size<n) size*=2;
tree.assign(2*size-1,0);
}
void build(vector <pair<ll,ll>> &a,ll x,ll lx,ll rx){
if(rx-lx==1){
if(lx<a.size()) tree[x]=a[lx].second-a[lx].first;
return;
}
else{
int m=(lx+rx)/2;
build(a,x*2+1,lx,m);
build(a,x*2+2,m,rx);
tree[x]=max(tree[x*2+1],tree[x*2+2]);
}
}
void build(vector <pair<ll,ll>> &a){
init(a.size());
build(a,0,0,size);
}
long long maxdo(ll l, ll r, ll x, ll lx, ll rx){
if(lx>=r || l>=rx) return 0;
if(lx>=l && rx<=r) return tree[x];
ll m=(lx+rx)/2;
ll s1=maxdo(l,r,x*2+1,lx,m);
ll s2=maxdo(l,r,x*2+2,m,rx);
return max(s1,s2);
}
long long maxdo(ll l,ll r){
return maxdo(l,r,0,0,size);
}
};
void solve(){
ll n;
cin>>n;
vector <pair<ll,ll>> a(n);
forn(i,n) cin>>a[i].first>>a[i].second;
sort(a.begin(),a.end());
vector <ll> p(n);p[0]=a[0].second;
for(int i=1;i<n;i++){
p[i]=p[i-1]+a[i].second;
}
vector <pair<ll,ll>> lol(n);
for(int i=0;i<n;i++){
lol[i].first=a[i].first;
lol[i].second=p[i];
}
segtree st;
st.init(lol.size());
st.build(lol);
ll ans=0;
for(int l=0;l<n;l++){
ll pl,al=a[l].first;
if(l==0) pl=0;
else pl=p[l-1];
ans=max(ans,st.maxdo(l,n)-pl+al);
}
cout<<ans;
}
signed main(){
speed;
int t=1;
while(t--){
solve();
}
}
Compilation message
art.cpp: In member function 'void segtree::build(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
art.cpp:24:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if(lx<a.size()) tree[x]=a[lx].second-a[lx].first;
| ~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
