#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 = inf, 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));
}
// for (int i = 0;i <= m;++i) {
// chmin(res, cal(i));
// }
cout << res << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7256 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 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 |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7256 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 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 |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7352 KB |
Output is correct |
16 |
Correct |
6 ms |
7276 KB |
Output is correct |
17 |
Correct |
6 ms |
7388 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
7 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
7 ms |
7292 KB |
Output is correct |
22 |
Correct |
6 ms |
7372 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
6 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 |
7256 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 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 |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7352 KB |
Output is correct |
16 |
Correct |
6 ms |
7276 KB |
Output is correct |
17 |
Correct |
6 ms |
7388 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
7 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
7 ms |
7292 KB |
Output is correct |
22 |
Correct |
6 ms |
7372 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
6 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 |
29 ms |
7628 KB |
Output is correct |
29 |
Correct |
30 ms |
7628 KB |
Output is correct |
30 |
Correct |
29 ms |
7628 KB |
Output is correct |
31 |
Correct |
29 ms |
7632 KB |
Output is correct |
32 |
Correct |
28 ms |
7632 KB |
Output is correct |
33 |
Correct |
29 ms |
7628 KB |
Output is correct |
34 |
Correct |
28 ms |
7632 KB |
Output is correct |
35 |
Correct |
28 ms |
7628 KB |
Output is correct |
36 |
Correct |
29 ms |
7628 KB |
Output is correct |
37 |
Correct |
29 ms |
7628 KB |
Output is correct |
38 |
Correct |
22 ms |
7628 KB |
Output is correct |
39 |
Correct |
23 ms |
7628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7256 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 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 |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7352 KB |
Output is correct |
16 |
Correct |
6 ms |
7276 KB |
Output is correct |
17 |
Correct |
6 ms |
7388 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
7 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
7 ms |
7292 KB |
Output is correct |
22 |
Correct |
6 ms |
7372 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
6 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 |
29 ms |
7628 KB |
Output is correct |
29 |
Correct |
30 ms |
7628 KB |
Output is correct |
30 |
Correct |
29 ms |
7628 KB |
Output is correct |
31 |
Correct |
29 ms |
7632 KB |
Output is correct |
32 |
Correct |
28 ms |
7632 KB |
Output is correct |
33 |
Correct |
29 ms |
7628 KB |
Output is correct |
34 |
Correct |
28 ms |
7632 KB |
Output is correct |
35 |
Correct |
28 ms |
7628 KB |
Output is correct |
36 |
Correct |
29 ms |
7628 KB |
Output is correct |
37 |
Correct |
29 ms |
7628 KB |
Output is correct |
38 |
Correct |
22 ms |
7628 KB |
Output is correct |
39 |
Correct |
23 ms |
7628 KB |
Output is correct |
40 |
Correct |
2212 ms |
18304 KB |
Output is correct |
41 |
Correct |
2249 ms |
19668 KB |
Output is correct |
42 |
Correct |
2053 ms |
19612 KB |
Output is correct |
43 |
Correct |
2276 ms |
19584 KB |
Output is correct |
44 |
Correct |
2587 ms |
19516 KB |
Output is correct |
45 |
Correct |
2424 ms |
19364 KB |
Output is correct |
46 |
Correct |
2503 ms |
18872 KB |
Output is correct |
47 |
Correct |
2460 ms |
19096 KB |
Output is correct |
48 |
Correct |
2095 ms |
19180 KB |
Output is correct |
49 |
Correct |
2087 ms |
18160 KB |
Output is correct |
50 |
Correct |
1944 ms |
18464 KB |
Output is correct |
51 |
Correct |
2005 ms |
18040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7256 KB |
Output is correct |
2 |
Correct |
4 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7244 KB |
Output is correct |
4 |
Correct |
5 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 |
5 ms |
7244 KB |
Output is correct |
13 |
Correct |
5 ms |
7244 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7352 KB |
Output is correct |
16 |
Correct |
6 ms |
7276 KB |
Output is correct |
17 |
Correct |
6 ms |
7388 KB |
Output is correct |
18 |
Correct |
6 ms |
7372 KB |
Output is correct |
19 |
Correct |
7 ms |
7372 KB |
Output is correct |
20 |
Correct |
6 ms |
7372 KB |
Output is correct |
21 |
Correct |
7 ms |
7292 KB |
Output is correct |
22 |
Correct |
6 ms |
7372 KB |
Output is correct |
23 |
Correct |
7 ms |
7372 KB |
Output is correct |
24 |
Correct |
6 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 |
29 ms |
7628 KB |
Output is correct |
29 |
Correct |
30 ms |
7628 KB |
Output is correct |
30 |
Correct |
29 ms |
7628 KB |
Output is correct |
31 |
Correct |
29 ms |
7632 KB |
Output is correct |
32 |
Correct |
28 ms |
7632 KB |
Output is correct |
33 |
Correct |
29 ms |
7628 KB |
Output is correct |
34 |
Correct |
28 ms |
7632 KB |
Output is correct |
35 |
Correct |
28 ms |
7628 KB |
Output is correct |
36 |
Correct |
29 ms |
7628 KB |
Output is correct |
37 |
Correct |
29 ms |
7628 KB |
Output is correct |
38 |
Correct |
22 ms |
7628 KB |
Output is correct |
39 |
Correct |
23 ms |
7628 KB |
Output is correct |
40 |
Correct |
2212 ms |
18304 KB |
Output is correct |
41 |
Correct |
2249 ms |
19668 KB |
Output is correct |
42 |
Correct |
2053 ms |
19612 KB |
Output is correct |
43 |
Correct |
2276 ms |
19584 KB |
Output is correct |
44 |
Correct |
2587 ms |
19516 KB |
Output is correct |
45 |
Correct |
2424 ms |
19364 KB |
Output is correct |
46 |
Correct |
2503 ms |
18872 KB |
Output is correct |
47 |
Correct |
2460 ms |
19096 KB |
Output is correct |
48 |
Correct |
2095 ms |
19180 KB |
Output is correct |
49 |
Correct |
2087 ms |
18160 KB |
Output is correct |
50 |
Correct |
1944 ms |
18464 KB |
Output is correct |
51 |
Correct |
2005 ms |
18040 KB |
Output is correct |
52 |
Correct |
3929 ms |
19720 KB |
Output is correct |
53 |
Correct |
3415 ms |
19260 KB |
Output is correct |
54 |
Correct |
3635 ms |
19584 KB |
Output is correct |
55 |
Correct |
3573 ms |
19392 KB |
Output is correct |
56 |
Correct |
3138 ms |
19400 KB |
Output is correct |
57 |
Correct |
3369 ms |
19096 KB |
Output is correct |
58 |
Correct |
3534 ms |
19036 KB |
Output is correct |
59 |
Correct |
2082 ms |
17752 KB |
Output is correct |