#include<bits/stdc++.h>
#define en "\n"
#define s second
#define f first
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vii vector<pair<int,int>>
#define int long long
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define loop(a) for(int i = 0; i < a; i++)
#define loopv(i,a) for (int i = 0; i < a; i++)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) printf("%.8f", x)
#define goog(tno) printf("Case #%d: ", tno)
using namespace std;
const int N = 500100;
int t[N*4];
void build (vector <int> a, int v, int tl, int tr) {
if (tl == tr)
t[v] = a[tl];
else {
int tm = (tl + tr) / 2;
build (a, v*2, tl, tm);
build (a, v*2+1, tm+1, tr);
t[v] = max(t[v*2], t[v*2+1]);
}
}
int sum (int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return max(sum (v*2, tl, tm, l, min(r,tm))
, sum (v*2+1, tm+1, tr, max(l,tm+1), r));
}
void solve() {
int n;
cin>>n;
vii a(n);
for(int i=0; i<n; i++){
cin>>a[i].f>>a[i].s;
}
sort(all(a));
for(int i=0; i<a.size()-1; i++){
if(a[i].f==a[i+1].f){
a[i+1].s+=a[i].s;
a.erase(a.begin()+i);
i--;
}
}
n=a.size();
// for(int i=0; i<n; i++){
// cout<<a[i].f<<" "<<a[i].s<<en;
// }
vi p(n+1, 0), pl(n+1, 0), pr(n+1, 0);
for(int i=0; i<n; i++){
p[i+1] = p[i] + a[i].s;
}
for(int i=1; i<=n; i++){
pl[i] = a[i-1].f - p[i-1];
}
for(int i=1; i<=n; i++){
pr[i] = p[i] - a[i-1].f;
}
// for(int i=0; i<n; i++){
// cout<<a[i].f<<" "<<a[i].s<<" "<<p[i+1]<<" "<<pl[i+1]<<" "<<pr[i+1]<<en;
// }
build(pl, 1, 0, n);
int mx1=0, mx2=0;
int ans=0;
for(int i=0; i<=n; i++){
ans=max(ans, sum(1, 0, n, 0, i-1) + pr[i]);
}
cout<<ans;
}
signed main() {
fast_io;
int tc = 1;
// scanf("%d", &tc);
while (tc--)
solve();
}
Compilation message
art.cpp: In function 'void solve()':
art.cpp:47:19: 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]
47 | for(int i=0; i<a.size()-1; i++){
| ~^~~~~~~~~~~
art.cpp:73:9: warning: unused variable 'mx1' [-Wunused-variable]
73 | int mx1=0, mx2=0;
| ^~~
art.cpp:73:16: warning: unused variable 'mx2' [-Wunused-variable]
73 | int mx1=0, mx2=0;
| ^~~
| # |
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 |
- |
