// Muallif: Mansuraliyev Husanboy Murotali o'g'li >> NamPS
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define vii vector<int>
#define vll vector<ll>
// 0-9 >> 48-57; A-Z>>65-90 and a-z>>97-122 respectively;
const ll mod=1e9+7;
ll t[400005];
void upd(ll x, ll l, ll r, ll ind, ll val){
//if(ind<l||ind>r) return;
if(l==r){
t[x]=val;return;
}
//if(ind<l||ind>r) return;
ll m=(l+r)/2;
if(ind<=m) upd(x*2,l,m,ind,val); else upd(x*2+1,m+1,r,ind,val);
t[x]=max(t[x*2],t[x*2+1]);
}
ll get(ll x, ll l, ll r, ll lx, ll rx){
if(lx<=l&&r<=rx){
return t[x];
}
if(l>rx||lx>r) return 0;
ll m=(l+r)/2;
return max(get(x*2,l,m,lx,rx),get(x*2+1,m+1,r,lx,rx));
}
void solve(){
int n; cin>>n;
vector<ll> x(n+1),g(n+1),en(n+1);
for(int i=1;i<=n;i++){
ll a,b,c; cin>>a>>b>>c;
x[i]=a; g[i]=g[i-1]+b,en[i]=en[i-1]+c;
}
vector<ll> dif(n+1); map<ll,int>mp;
multiset<ll> st;
//ll mn=1e18,mx=-1e18;
for(int i=1;i<=n;i++){
x[i]-=x[1];
dif[i]=en[i]-x[i];
st.insert(dif[i]);
//mn=min(mn,dif[i]); mx=max(mx,dif[i]);
mp[dif[i]]=max(i,mp[dif[i]]);
}ll ans=0;
ll mn=1,mx=mp.size(); ll cur=1;
map<ll,ll> indtree;
for(auto u:mp){
indtree[u.F]=cur;
cur++;
}
for(auto u:mp){
//cout<<"d"<<endl;
upd(1,mn,mx,indtree[u.F],u.S);
}
// cout<<"a"<<endl;
for(int i=1;i<=n;i++){
ans=max(ans,g[get(1,mn,mx,indtree[*st.lower_bound(en[i-1]-x[i])],indtree[*--st.end()])]-g[i-1]);
// cout<<i<<": "<<get(1,mn,mx,indtree[*st.lower_bound(en[i-1]-x[i])],indtree[*--st.end()])<<endl;
st.erase(st.find(dif[i]));
// cout<<ans<<endl;
}
cout<<ans;
}
int main(){
ios;
// int t; cin>>t; while(t--)
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
464 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
500 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
724 KB |
Output is correct |
23 |
Correct |
6 ms |
1492 KB |
Output is correct |
24 |
Correct |
7 ms |
1592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
464 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
500 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
724 KB |
Output is correct |
23 |
Correct |
6 ms |
1492 KB |
Output is correct |
24 |
Correct |
7 ms |
1592 KB |
Output is correct |
25 |
Correct |
6 ms |
1492 KB |
Output is correct |
26 |
Correct |
11 ms |
2724 KB |
Output is correct |
27 |
Correct |
12 ms |
2772 KB |
Output is correct |
28 |
Correct |
75 ms |
12544 KB |
Output is correct |
29 |
Correct |
72 ms |
12828 KB |
Output is correct |
30 |
Correct |
162 ms |
25568 KB |
Output is correct |
31 |
Correct |
157 ms |
24464 KB |
Output is correct |
32 |
Correct |
159 ms |
24532 KB |
Output is correct |
33 |
Correct |
140 ms |
24288 KB |
Output is correct |
34 |
Correct |
152 ms |
24056 KB |
Output is correct |
35 |
Correct |
156 ms |
24912 KB |
Output is correct |
36 |
Correct |
150 ms |
25152 KB |
Output is correct |