#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
vi allPos;
class Node {
public:
ll data = -1e9;
ll lazy = 0;
ll dn,up;
Node *left;
Node *right;
bool hasChildren = false;
Node(ll dn,ll up):dn(dn),up(up){
}
void ensure(){
if(dn+1==up) return;
if(!hasChildren){
left = new Node(dn,(dn+up)/2);
right = new Node((dn+up)/2,up);
hasChildren = true;
}
left->data+=lazy;
left->lazy+=lazy;
right->data+=lazy;
right->lazy+=lazy;
lazy = 0;
}
ll trans(ll ind){
return lower_bound(all(allPos),ind)-allPos.begin();
}
void _add(ll a,ll b,ll val){
add(trans(a),trans(b),val);
}
ll add(ll a,ll b,ll val){
if(a>=up||b<=dn) return data;
if(a<=dn&&up<=b){
data += val;
lazy += val;
return data;
} else {
ensure();
return data = max(left->add(a,b,val),right->add(a,b,val));
}
}
void _update(ll a,ll val){
update(trans(a),val);
}
void update(ll pos,ll val){
ll diff = val-query(pos,pos+1);
if(diff>0)
add(pos,pos+1,diff);
}
ll _query(ll a,ll b){
return query(trans(a),trans(b));
}
ll query(ll a,ll b){
if(a>=up||b<=dn) return -1e18;
if(a<=dn&&up<=b) return data;
ensure();
return max(left->query(a,b),right->query(a,b));
}
};
int main(){
cin.sync_with_stdio(false);
/*srand(5);
ll n = 200;
Node st(0,n);
vi v(n,-1e18);
rep(i,0,300){
ll q = rand()%3;
ll b = rand()%n+1;
ll a = rand()%b;
ll val = rand()%100;
//cout<<q<<" "<<a<<" "<<b<<" "<<val<<endl;
if(q==0){
rep(i,a,b) v[i] += val;
st.add(a,b,val);
} else if(q==1){
ll mx = -1e18;
rep(i,a,b) mx = max(mx,v[i]);
if(mx!=st.query(a,b)){
rep(i,0,n) cout<<v[i]<<" ";
cout<<endl;
cout<<mx<<endl;
rep(i,0,n) cout<<st.query(i,i+1)<<" ";
cout<<endl;
cout<<st.query(a,b)<<endl;
assert(false);
}
} else {
v[b-1] = max(v[b-1],val);
st.update(b-1,val);
}
}
cout<<endl;*/
ll n; cin>>n;
vi x(n);
vi g(n);
vi d(n);
rep(i,0,n){
cin>>x[i]>>g[i]>>d[i];
}
ll currentZero = 0;
ll lastX = x[0];
set<ll> allPosSet;
allPosSet.insert(-1e9);
allPosSet.insert(1e9);
rep(i,0,n){
ll dx = x[i]-lastX;
lastX = x[i];
currentZero -= ( d[i]-dx);
allPosSet.insert(currentZero+d[i]);
allPosSet.insert(currentZero);
}
trav(pos,allPosSet) allPos.push_back(pos);
Node st(0,allPos.size());
currentZero = 0;
lastX = x[0];
ll best = 0;
rep(i,0,n){
ll dx = x[i]-lastX;
lastX = x[i];
ll energy = d[i]-dx;
st._add(-1e9,1e9,g[i]);
currentZero -= energy;
st._update(currentZero+d[i],g[i]);
best = max(best,st._query(currentZero,1e9));
}
cout<<best<<endl;
_Exit(0);
}
Compilation message
divide.cpp: In function 'int main()':
divide.cpp:82:14: warning: 'st.Node::right' may be used uninitialized in this function [-Wmaybe-uninitialized]
return max(left->query(a,b),right->query(a,b));
^~~~
divide.cpp:149:10: note: 'st.Node::right' was declared here
Node st(0,allPos.size());
^~
divide.cpp:82:14: warning: 'st.Node::left' may be used uninitialized in this function [-Wmaybe-uninitialized]
return max(left->query(a,b),right->query(a,b));
^~~~
divide.cpp:149:10: note: 'st.Node::left' was declared here
Node st(0,allPos.size());
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
488 KB |
Output is correct |
| 3 |
Correct |
3 ms |
488 KB |
Output is correct |
| 4 |
Correct |
3 ms |
576 KB |
Output is correct |
| 5 |
Correct |
3 ms |
576 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
576 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
576 KB |
Output is correct |
| 2 |
Correct |
2 ms |
680 KB |
Output is correct |
| 3 |
Correct |
3 ms |
724 KB |
Output is correct |
| 4 |
Correct |
5 ms |
868 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
876 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
2540 KB |
Output is correct |
| 2 |
Correct |
23 ms |
4456 KB |
Output is correct |
| 3 |
Correct |
25 ms |
4456 KB |
Output is correct |
| 4 |
Correct |
120 ms |
20876 KB |
Output is correct |
| 5 |
Correct |
129 ms |
22184 KB |
Output is correct |
| 6 |
Correct |
265 ms |
44396 KB |
Output is correct |
| 7 |
Correct |
301 ms |
46312 KB |
Output is correct |
| 8 |
Correct |
262 ms |
48260 KB |
Output is correct |
| 9 |
Correct |
231 ms |
49928 KB |
Output is correct |
| 10 |
Incorrect |
227 ms |
50516 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
