#include <bits/stdc++.h>
#define maxn 200000
#define s second
#define f first
using namespace std;
typedef pair<int,int> ii;
typedef vector <ii> vii;
typedef vector <int> vi;
int seg[4*maxn], lazy[4*maxn];
void unlazy(int u){
seg[u]+=lazy[u];
lazy[(2*u)] += lazy[u];
lazy[(2*u)+1] += lazy[u];
lazy[u]=0;
}
void update(int u, int l, int r, int ql, int qr, int c){
int mid;
mid = (l+r)/2;
unlazy(u);
if(ql>r || qr<l) mid=0;
else{
if(l>=ql && r<=qr) lazy[u]+=c;
else{
update(2*u, l, mid, ql, qr, c);
update((2*u)+1, mid+1, r, ql, qr, c);
seg[u] = max(seg[2*u], seg[(2*u)+1]);
}
unlazy(u);
}
}
int main(){
int n, i, m, people[maxn], a, b, ant, atu;
vii stations, v;
cin >> n >> m;
for(i=0;i<m;i++){
cin >> a >> b >> people[i];
if(a>b) swap(a,b);
stations.push_back({a, b});
v.push_back({b-a, i});
}
sort(v.begin(), v.end());
for(i=0;i<m;i++){
update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, people[v[i].s]);
}
for(i=m-1;i>=0;i--){
unlazy(1);
ant = seg[1];
update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, -people[v[i].s]);
if(stations[v[i].s].f) update(1, 0, n-1, 0, stations[v[i].s].f-1, people[v[i].s]);
update(1, 0, n-1, stations[v[i].s].s, n-1, people[v[i].s]);
unlazy(1);
atu = seg[1];
if(ant<=atu){
update(1, 0, n-1, stations[v[i].s].f, stations[v[i].s].s-1, people[v[i].s]);
if(stations[v[i].s].f) update(1, 0, n-1, 0, stations[v[i].s].f-1, -people[v[i].s]);
update(1, 0, n-1, stations[v[i].s].s, n-1, -people[v[i].s]);
}
}
cout << seg[1] << endl;
return (0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
1088 KB |
Output is correct |
6 |
Correct |
1 ms |
1088 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
1088 KB |
Output is correct |
9 |
Correct |
1 ms |
1192 KB |
Output is correct |
10 |
Correct |
1 ms |
1088 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Incorrect |
1 ms |
1084 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
1088 KB |
Output is correct |
6 |
Correct |
1 ms |
1088 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
1088 KB |
Output is correct |
9 |
Correct |
1 ms |
1192 KB |
Output is correct |
10 |
Correct |
1 ms |
1088 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Incorrect |
1 ms |
1084 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
1088 KB |
Output is correct |
6 |
Correct |
1 ms |
1088 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
1088 KB |
Output is correct |
9 |
Correct |
1 ms |
1192 KB |
Output is correct |
10 |
Correct |
1 ms |
1088 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Incorrect |
1 ms |
1084 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
1088 KB |
Output is correct |
6 |
Correct |
1 ms |
1088 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
1088 KB |
Output is correct |
9 |
Correct |
1 ms |
1192 KB |
Output is correct |
10 |
Correct |
1 ms |
1088 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Incorrect |
1 ms |
1084 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
1088 KB |
Output is correct |
6 |
Correct |
1 ms |
1088 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
1088 KB |
Output is correct |
9 |
Correct |
1 ms |
1192 KB |
Output is correct |
10 |
Correct |
1 ms |
1088 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Incorrect |
1 ms |
1084 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |