#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,zx,xc,fen[200009],jmz[100009],jmx[100009],pas;
pair <pair <long long, long long>, long long> p[100009];
map <long long, long long> m;
map <long long, long long>::iterator it;
long long read(long long q){
if(q<=0) return 0;
long long mn=fen[q];
while(q>0){
if(mn>fen[q]) mn=fen[q];
q=q-(q&(-q));
}
return mn;
}
void upd(long long q, long long w){
while(q<=200002){
if(fen[q]>w) fen[q]=w;
q=q+(q&(-q));
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(b=1; b<=a; b++){
cin>>p[b].first.first>>p[b].first.second>>p[b].second;
swap(p[b].first.second,p[b].second);
if(pas<p[b].second) pas=p[b].second;
jmz[b]=p[b].first.second+jmz[b-1];
jmx[b]=jmx[b-1]+p[b].second;
p[b].first.first++;
m[jmz[b-1]-p[b].first.first]=1;
m[jmz[b]-p[b].first.first]=1;
}
c=0;
for(it=m.begin(); it!=m.end(); it++){
c++;
m[(*it).first]=c;
}
for(b=0; b<=200005; b++) fen[b]=999999999999999999LL;
for(b=1; b<=a; b++){
c=read(m[jmz[b]-p[b].first.first]);
if(pas<jmx[b]-c) pas=jmx[b]-c;
upd(m[jmz[b-1]-p[b].first.first],jmx[b-1]);
}
cout<<pas;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1912 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1912 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1912 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1912 KB |
Output is correct |
| 7 |
Correct |
13 ms |
1912 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1912 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1912 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1960 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1960 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2040 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2012 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2040 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2168 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2040 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2040 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2168 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2296 KB |
Output is correct |
| 11 |
Correct |
10 ms |
2808 KB |
Output is correct |
| 12 |
Correct |
10 ms |
2808 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3704 KB |
Output is correct |
| 3 |
Correct |
15 ms |
3832 KB |
Output is correct |
| 4 |
Correct |
65 ms |
11128 KB |
Output is correct |
| 5 |
Correct |
69 ms |
11548 KB |
Output is correct |
| 6 |
Correct |
202 ms |
21196 KB |
Output is correct |
| 7 |
Correct |
181 ms |
20344 KB |
Output is correct |
| 8 |
Correct |
188 ms |
20348 KB |
Output is correct |
| 9 |
Correct |
127 ms |
20088 KB |
Output is correct |
| 10 |
Correct |
150 ms |
19576 KB |
Output is correct |
| 11 |
Correct |
178 ms |
20472 KB |
Output is correct |
| 12 |
Correct |
132 ms |
20760 KB |
Output is correct |
