#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
const ll inf = 1ll << 55;
int n, m;
vector<pair<int,ll>> rc[MAX_N];
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
vector<tuple<int,int,int>> req(m);
for (auto &[l, r, c] : req) {
cin >> l >> r >> c;
if (l > r) swap(l, r);
//assert(c == 1);
}
vector<ll> sum(n + 10);
for (auto [l, r, c] : req)
sum[l] += c, sum[r] -= c;
for (auto [l, r, c] : req) rc[l].pb(r, c);
auto cal = [&](ll mx) {
// first is right end, second is count
priority_queue<pair<int,ll>> pq;
vector<ll> pfsum(sum);
ll use = 0;
for (int i = 1;i <= n;++i) {
for (auto [r, c] : rc[i])
pq.emplace(r, c);
pfsum[i] += pfsum[i-1];
while (pfsum[i] > mx) {
assert(pq.size());
auto [r, c] = pq.top(); pq.pop();
ll req = min(c, (pfsum[i] - mx + 1) / 2);
use += req;
pfsum[i] -= req * 2;
pfsum[r] += req * 2;
if (req < c) pq.emplace(r, c - req);
}
}
return mx + use;
};
ll res = inf;
for (int i : {0, 1}) {
ll l = 0, r = 1e14 / 2, mid;
while (l < r) {
mid = l + r >> 1;
ll x = (mid*2) + i, y = x + 2;
if (cal(x) <= cal(y))
r = mid;
else
l = mid+1;
}
chmin(res, cal(l*2 + i));
}
cout << res << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7244 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7244 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7316 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7244 KB |
Output is correct |
15 |
Correct |
4 ms |
7244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7244 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7244 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7316 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7244 KB |
Output is correct |
15 |
Correct |
4 ms |
7244 KB |
Output is correct |
16 |
Correct |
6 ms |
7372 KB |
Output is correct |
17 |
Correct |
6 ms |
7276 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
6 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
6 ms |
7372 KB |
Output is correct |
22 |
Correct |
6 ms |
7332 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
7 ms |
7372 KB |
Output is correct |
25 |
Correct |
6 ms |
7372 KB |
Output is correct |
26 |
Correct |
6 ms |
7372 KB |
Output is correct |
27 |
Correct |
6 ms |
7372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7244 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7244 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7316 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7244 KB |
Output is correct |
15 |
Correct |
4 ms |
7244 KB |
Output is correct |
16 |
Correct |
6 ms |
7372 KB |
Output is correct |
17 |
Correct |
6 ms |
7276 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
6 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
6 ms |
7372 KB |
Output is correct |
22 |
Correct |
6 ms |
7332 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
7 ms |
7372 KB |
Output is correct |
25 |
Correct |
6 ms |
7372 KB |
Output is correct |
26 |
Correct |
6 ms |
7372 KB |
Output is correct |
27 |
Correct |
6 ms |
7372 KB |
Output is correct |
28 |
Correct |
26 ms |
7620 KB |
Output is correct |
29 |
Correct |
27 ms |
7632 KB |
Output is correct |
30 |
Correct |
29 ms |
7600 KB |
Output is correct |
31 |
Correct |
26 ms |
7632 KB |
Output is correct |
32 |
Correct |
24 ms |
7636 KB |
Output is correct |
33 |
Correct |
28 ms |
7628 KB |
Output is correct |
34 |
Correct |
25 ms |
7624 KB |
Output is correct |
35 |
Correct |
25 ms |
7628 KB |
Output is correct |
36 |
Correct |
25 ms |
7628 KB |
Output is correct |
37 |
Correct |
25 ms |
7628 KB |
Output is correct |
38 |
Correct |
21 ms |
7756 KB |
Output is correct |
39 |
Correct |
20 ms |
7640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7244 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7244 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7316 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7244 KB |
Output is correct |
15 |
Correct |
4 ms |
7244 KB |
Output is correct |
16 |
Correct |
6 ms |
7372 KB |
Output is correct |
17 |
Correct |
6 ms |
7276 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
6 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
6 ms |
7372 KB |
Output is correct |
22 |
Correct |
6 ms |
7332 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
7 ms |
7372 KB |
Output is correct |
25 |
Correct |
6 ms |
7372 KB |
Output is correct |
26 |
Correct |
6 ms |
7372 KB |
Output is correct |
27 |
Correct |
6 ms |
7372 KB |
Output is correct |
28 |
Correct |
26 ms |
7620 KB |
Output is correct |
29 |
Correct |
27 ms |
7632 KB |
Output is correct |
30 |
Correct |
29 ms |
7600 KB |
Output is correct |
31 |
Correct |
26 ms |
7632 KB |
Output is correct |
32 |
Correct |
24 ms |
7636 KB |
Output is correct |
33 |
Correct |
28 ms |
7628 KB |
Output is correct |
34 |
Correct |
25 ms |
7624 KB |
Output is correct |
35 |
Correct |
25 ms |
7628 KB |
Output is correct |
36 |
Correct |
25 ms |
7628 KB |
Output is correct |
37 |
Correct |
25 ms |
7628 KB |
Output is correct |
38 |
Correct |
21 ms |
7756 KB |
Output is correct |
39 |
Correct |
20 ms |
7640 KB |
Output is correct |
40 |
Correct |
1858 ms |
18244 KB |
Output is correct |
41 |
Correct |
1917 ms |
18312 KB |
Output is correct |
42 |
Correct |
1710 ms |
17932 KB |
Output is correct |
43 |
Correct |
1778 ms |
17996 KB |
Output is correct |
44 |
Correct |
1812 ms |
18136 KB |
Output is correct |
45 |
Correct |
1675 ms |
17956 KB |
Output is correct |
46 |
Correct |
1668 ms |
17640 KB |
Output is correct |
47 |
Correct |
1755 ms |
17624 KB |
Output is correct |
48 |
Correct |
1627 ms |
17508 KB |
Output is correct |
49 |
Correct |
1559 ms |
16612 KB |
Output is correct |
50 |
Correct |
1471 ms |
16924 KB |
Output is correct |
51 |
Correct |
1609 ms |
16672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
4 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7244 KB |
Output is correct |
6 |
Correct |
4 ms |
7244 KB |
Output is correct |
7 |
Correct |
4 ms |
7244 KB |
Output is correct |
8 |
Correct |
4 ms |
7244 KB |
Output is correct |
9 |
Correct |
4 ms |
7244 KB |
Output is correct |
10 |
Correct |
4 ms |
7244 KB |
Output is correct |
11 |
Correct |
4 ms |
7244 KB |
Output is correct |
12 |
Correct |
4 ms |
7316 KB |
Output is correct |
13 |
Correct |
4 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7244 KB |
Output is correct |
15 |
Correct |
4 ms |
7244 KB |
Output is correct |
16 |
Correct |
6 ms |
7372 KB |
Output is correct |
17 |
Correct |
6 ms |
7276 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
6 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
6 ms |
7372 KB |
Output is correct |
22 |
Correct |
6 ms |
7332 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
7 ms |
7372 KB |
Output is correct |
25 |
Correct |
6 ms |
7372 KB |
Output is correct |
26 |
Correct |
6 ms |
7372 KB |
Output is correct |
27 |
Correct |
6 ms |
7372 KB |
Output is correct |
28 |
Correct |
26 ms |
7620 KB |
Output is correct |
29 |
Correct |
27 ms |
7632 KB |
Output is correct |
30 |
Correct |
29 ms |
7600 KB |
Output is correct |
31 |
Correct |
26 ms |
7632 KB |
Output is correct |
32 |
Correct |
24 ms |
7636 KB |
Output is correct |
33 |
Correct |
28 ms |
7628 KB |
Output is correct |
34 |
Correct |
25 ms |
7624 KB |
Output is correct |
35 |
Correct |
25 ms |
7628 KB |
Output is correct |
36 |
Correct |
25 ms |
7628 KB |
Output is correct |
37 |
Correct |
25 ms |
7628 KB |
Output is correct |
38 |
Correct |
21 ms |
7756 KB |
Output is correct |
39 |
Correct |
20 ms |
7640 KB |
Output is correct |
40 |
Correct |
1858 ms |
18244 KB |
Output is correct |
41 |
Correct |
1917 ms |
18312 KB |
Output is correct |
42 |
Correct |
1710 ms |
17932 KB |
Output is correct |
43 |
Correct |
1778 ms |
17996 KB |
Output is correct |
44 |
Correct |
1812 ms |
18136 KB |
Output is correct |
45 |
Correct |
1675 ms |
17956 KB |
Output is correct |
46 |
Correct |
1668 ms |
17640 KB |
Output is correct |
47 |
Correct |
1755 ms |
17624 KB |
Output is correct |
48 |
Correct |
1627 ms |
17508 KB |
Output is correct |
49 |
Correct |
1559 ms |
16612 KB |
Output is correct |
50 |
Correct |
1471 ms |
16924 KB |
Output is correct |
51 |
Correct |
1609 ms |
16672 KB |
Output is correct |
52 |
Correct |
3326 ms |
18036 KB |
Output is correct |
53 |
Correct |
3009 ms |
17908 KB |
Output is correct |
54 |
Correct |
3194 ms |
18044 KB |
Output is correct |
55 |
Correct |
3166 ms |
17924 KB |
Output is correct |
56 |
Correct |
2835 ms |
17928 KB |
Output is correct |
57 |
Correct |
3016 ms |
17552 KB |
Output is correct |
58 |
Correct |
3125 ms |
17544 KB |
Output is correct |
59 |
Correct |
1770 ms |
16480 KB |
Output is correct |