#include <bits/stdc++.h>
using namespace std;
#define int long long
struct segTree {
const int nothing = -1e9;
vector<int> val, lazy;
int n;
int f(int a, int b) { return max(a, b); }
inline void pushdown(int cur) {
if (lazy[cur])
val[cur] += lazy[cur];
if (cur < n && lazy[cur]) {
lazy[cur << 1] += lazy[cur];
lazy[cur << 1 | 1] += lazy[cur];
}
lazy[cur] = 0;
}
void update(int l, int r, int value, int cur = 1, int ll = 1, int rr = 1e9) {
rr = min(rr, n);
pushdown(cur);
if (l > r)
return;
if (l == ll && r == rr) {
lazy[cur] = value;
pushdown(cur);
return;
}
int mid = (ll + rr) >> 1;
update(l, min(r, mid), value, cur << 1, ll, mid);
update(max(l, mid + 1), r, value, cur << 1 | 1, mid + 1, rr);
val[cur] = f(val[cur << 1], val[cur << 1 | 1]);
}
int query(int l, int r, int cur = 1, int ll = 1, int rr = 1e9) {
rr = min(rr, n);
pushdown(cur);
if (l > r)
return nothing;
if (l == ll && r == rr)
return val[cur];
int mid = (ll + rr) >> 1;
return f(query(l, min(r, mid), cur << 1, ll, mid), query(max(l, mid + 1), r, cur << 1 | 1, mid + 1, rr));
}
segTree(vector<int> arr) {
for (n = arr.size(); n & (n - 1); n++) {}
val = vector<int>(n * 2, nothing);
lazy = vector<int>(n * 2, 0);
for (int i = n + arr.size() - 1; i; i--)
val[i] = ((i < n) ? f(val[i << 1], val[i << 1 | 1]) : arr[i - n]);
}
};
signed main() {
int n; cin >> n;
pair<int, int> p[n];
for (int i = 0; i < n; ++i) {
cin >> p[i].first >> p[i].second;
}
sort(p, p + n);
vector<int> d(n);
int s = 0;
for (int i = 0; i < n; ++i) {
s += p[i].second;
d[i] = s - p[i].first;
}
segTree st(d);
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, st.query(i + 1, n) + p[i].first);
st.update(i + 1, n, -p[i].second);
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
