This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |