#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M;
struct Info {
int a, b, c, id;
bool operator <(const Info &i) const {
return id < i.id;
}
};
set<Info> st;
ll arr[200010];
struct node {
ll mx1, mx2, l, r;
};
node mrg(node &a, node &b) {
node ret;
if(abs(a.mx1 - b.mx1) < 2) {
ret.mx1 = a.mx1;
ret.mx2 = max(a.mx2, b.mx2);
ret.l = min(a.l, b.l);
ret.r = max(a.r, b.r);
}
else if(a.mx1 > b.mx1) {
ret.mx1 = a.mx1;
ret.mx2 = max(a.mx2, b.mx1);
ret.l = a.l;
ret.r = a.r;
}
else {
ret.mx1 = b.mx1;
ret.mx2 = max(a.mx1, b.mx2);
ret.l = b.l;
ret.r = b.r;
}
return ret;
}
struct BIT {
vector<node> tree;
vector<ll> lazy;
void init() {
tree = vector<node>(4 * N);
lazy = vector<ll>(4 * N, 0);
build(0, N - 1, 1);
}
void build(int l, int r, int n) {
if(l == r) {
tree[n] = {arr[l], (ll)-1e18, l, l};
return;
}
int m = (l + r)>>1;
build(l, m, 2*n);
build(m + 1, r, 2*n + 1);
tree[n] = mrg(tree[2*n], tree[2*n + 1]);
}
void prop(int l, int r, int n) {
if(l != r) {
tree[2*n].mx1 += lazy[n];
tree[2*n].mx2 += lazy[n];
lazy[2*n] += lazy[n];
tree[2*n + 1].mx1 += lazy[n];
tree[2*n + 1].mx2 += lazy[n];
lazy[2*n + 1] += lazy[n];
lazy[n] = 0;
}
}
void upd(int a, int b, ll d, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n].mx1 += d;
tree[n].mx2 += d;
lazy[n] += d;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd(a, b, d, l, m, 2*n);
upd(a, b, d, m + 1, r, 2*n + 1);
tree[n] = mrg(tree[2*n], tree[2*n + 1]);
}
} bit;
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < M; i++) {
int a, b, c; scanf("%d %d %d", &a, &b, &c);
a--; b--;
if(a > b) swap(a, b);
arr[a] += c;
arr[b] -= c;
st.insert({ a, b, c, i });
}
ll ans = arr[0];
for(int i = 1; i < N; i++) {
arr[i] += arr[i - 1];
ans = max(ans, arr[i]);
}
bit.init();
while(1) {
node t = bit.tree[1];
set<Info>::iterator it;
while(st.size()) {
it = st.begin();
if(!(it->a <= t.l && t.r < it->b)) {
st.erase(it);
}
else break;
}
if(!st.size()) break;
Info tmp = *it;
st.erase(st.find(tmp));
if(t.mx1 - t.mx2 <= 2 * tmp.c) {
bit.upd(tmp.a, tmp.b - 1, -(t.mx1 - t.mx2) / 2 * 2, 0, N - 1, 1);
tmp.c -= (t.mx1 - t.mx2) / 2;
ans -= (t.mx1 - t.mx2) / 2;
st.insert(tmp);
}
else {
bit.upd(tmp.a, tmp.b - 1, -tmp.c * 2, 0, N - 1, 1);
ans -= tmp.c;
}
}
printf("%lld", ans);
}
Compilation message
arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
arranging_tickets.cpp:92:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b, c; scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
