#include <bits/stdc++.h>
using namespace std;
// Solution:
// We can binary search the answer. We also break the circle to
// a line segment.
//
// If intervals [a, b] and [c, d] is reversed, and a < b < c < d,
// then we originally have interval values:
// ([1, a), 0), ([a, b], 1), ((b, c), 0), ([c, d], 1), ((d, N], 0)
// and reversed values are:
// ([1, a), 2), ([a, b], 1), ((b, c), 2), ([c, d], 1), ((d, N], 2)
// We can see that all regions increased - thus all flipped intervals
// must share a point t.
//
// For a fixed point t, let a[i] be the sum of people travelling through i,
// and b[i] be the final one once we reversed optimally. Then b[t] = max(b[i])
// or b[t] = max(b[i]) - 1. This allows us to check only a[t] - max_ans and
// a[t] - max_ans + 1 flips for a point t, where max_ans is the current
// mid in the binary search. Proof follows.
//
// Assume then b[t] < max(b[i]) - 1. Then we can find two reversed segments [a, b] and
// [c, d], such that a is the minimum coordinate of reversed segment and d is the
// maximum one of reversed segments. By definition, [a, b] and [c, d] passes through t,
// and we can unreverse them. This will not change max(b[i]), and increment b[t] by either
// 1 or 2. Thus we can keep doing this until the condition is satisfied without breaking
// the solution.
//
// This yields an O(M^2 log^2 M) solution. We can further speed this up by noticing that
// we only need to check t where a[t] = max(a[i]) and t is the minimum and maximum i that
// is equal max(a[i]). Why? Since b[i] - a[i] is smaller the closer i is to t, let j not be
// in the common interval of all reversed intervals. Then b[t] - a[t] + 1 <= b[j] - a[j].
// If we assume a[t] + 1 <= a[j], we can sum them to get b[t] + 2 <= b[j]. But by definition
// b[t] = max(b[i]) or b[t] = max(b[i]) - 1, thus we get a contradiction. Therefore, a[t] =
// max(a[i]) must be satisfied.
//
// Now we prove the second condition (only checking the leftmost and rightmost t such that a[t] =
// max(a[i])). First, there is no reversed interval [x, y], such that l < x < y < r. Assume otherwise.
// Then, when we reverse [x, y], let b' be the resulting arrangement. We have b'[t] = b[t] + 1
// and b'[l] = b[l] - 1, and b'[l] >= b'[t] since we use t = l. Then we get b[l] >= b[t] + 2 which
// is a contradiction since b[t] = max(b[i]) or b[t] = max(b[i]) - 1. Thus no such [x, y] exist, which
// means we only need to consider t = l or t = r.
//
// After we determine max_ans and t, we can do the reversal greedily. We can use a segment tree or a
// priority queue to support the operations: point update += x at position i and remove x items from
// the right to simulate the greedy selection. We check after we do all flips to see if we satisfy
// everything.
//
// Time: O(N log^2 N)
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int N, M;
cin >> N >> M;
vector<int> A(M), B(M), C(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i] >> C[i];
A[i]--, B[i]--;
if (A[i] > B[i]) {
swap(A[i], B[i]);
}
}
vector<long long> sum(N);
vector<vector<pair<int, int>>> segs(N);
for (int i = 0; i < M; i++) {
sum[A[i]] += C[i];
sum[B[i]] -= C[i];
segs[A[i]].emplace_back(B[i], C[i]);
}
for (int i = 1; i < N; i++) {
sum[i] += sum[i - 1];
}
long long mx = *max_element(begin(sum), end(sum));
int ll = -1, rr = -1;
for (int i = 0; i < N; i++) {
if (sum[i] == mx) {
ll = i;
break;
}
}
for (int i = N - 1; i >= 0; i--) {
if (sum[i] == mx) {
rr = i;
break;
}
}
auto Check = [&](int t, long long mx, long long flips) -> bool {
vector<long long> upd_sum(N);
for (int i = 1; i < N; i++) {
upd_sum[i] += upd_sum[i - 1];
}
long long flipped = 0;
priority_queue<array<int, 3>> pq;
for (int pos = 0; pos <= t; pos++) {
for (auto i : segs[pos]) {
if (i.first > t) {
pq.push({i.first, pos, i.second});
}
}
// Look at effects to upd_sum for derivation, sum[pos] += 2 * constant
long long need = (sum[pos] - mx + flips + 1) / 2;
if (pos == t) need = flips;
need = max(need - flipped, 0ll);
flipped += need;
while (need > 0) {
if (pq.empty()) {
return false;
}
auto arr = pq.top(); pq.pop();
long long del = min(need, 1ll * arr[2]);
arr[2] -= del, need -= del;
if (arr[2] > 0) {
pq.push(arr);
}
// Add [0, A) and [B, N)
upd_sum[0] += del;
upd_sum[arr[1]] -= del;
upd_sum[arr[0]] += del;
// Undo [A, B)
upd_sum[arr[1]] -= del;
upd_sum[arr[0]] += del;
}
}
for (int i = 0; i < N; i++) {
if (i > 0) {
upd_sum[i] += upd_sum[i - 1];
}
if (sum[i] + upd_sum[i] > mx) {
return false;
}
}
return true;
};
auto CheckAll = [&](long long m) -> bool {
return Check(ll, m, sum[ll] - m + 0) ||
Check(ll, m, sum[ll] - m + 1) ||
Check(rr, m, sum[rr] - m + 0) ||
Check(rr, m, sum[rr] - m + 1);
};
long long lo = 0, hi = mx;
while (lo < hi) {
long long md = (lo + hi) / 2;
if (CheckAll(md)) {
hi = md;
} else {
lo = md + 1;
}
}
cout << lo << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
4 ms |
640 KB |
Output is correct |
29 |
Correct |
4 ms |
640 KB |
Output is correct |
30 |
Correct |
4 ms |
640 KB |
Output is correct |
31 |
Correct |
4 ms |
640 KB |
Output is correct |
32 |
Correct |
6 ms |
640 KB |
Output is correct |
33 |
Correct |
5 ms |
640 KB |
Output is correct |
34 |
Correct |
3 ms |
640 KB |
Output is correct |
35 |
Correct |
5 ms |
640 KB |
Output is correct |
36 |
Correct |
6 ms |
640 KB |
Output is correct |
37 |
Correct |
2 ms |
656 KB |
Output is correct |
38 |
Correct |
2 ms |
640 KB |
Output is correct |
39 |
Correct |
2 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
4 ms |
640 KB |
Output is correct |
29 |
Correct |
4 ms |
640 KB |
Output is correct |
30 |
Correct |
4 ms |
640 KB |
Output is correct |
31 |
Correct |
4 ms |
640 KB |
Output is correct |
32 |
Correct |
6 ms |
640 KB |
Output is correct |
33 |
Correct |
5 ms |
640 KB |
Output is correct |
34 |
Correct |
3 ms |
640 KB |
Output is correct |
35 |
Correct |
5 ms |
640 KB |
Output is correct |
36 |
Correct |
6 ms |
640 KB |
Output is correct |
37 |
Correct |
2 ms |
656 KB |
Output is correct |
38 |
Correct |
2 ms |
640 KB |
Output is correct |
39 |
Correct |
2 ms |
640 KB |
Output is correct |
40 |
Correct |
268 ms |
14428 KB |
Output is correct |
41 |
Correct |
307 ms |
14804 KB |
Output is correct |
42 |
Correct |
255 ms |
14300 KB |
Output is correct |
43 |
Correct |
425 ms |
14300 KB |
Output is correct |
44 |
Correct |
222 ms |
14428 KB |
Output is correct |
45 |
Correct |
507 ms |
14096 KB |
Output is correct |
46 |
Correct |
312 ms |
14048 KB |
Output is correct |
47 |
Correct |
108 ms |
13556 KB |
Output is correct |
48 |
Correct |
117 ms |
13692 KB |
Output is correct |
49 |
Correct |
80 ms |
10184 KB |
Output is correct |
50 |
Correct |
62 ms |
9924 KB |
Output is correct |
51 |
Correct |
77 ms |
9788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
4 ms |
640 KB |
Output is correct |
29 |
Correct |
4 ms |
640 KB |
Output is correct |
30 |
Correct |
4 ms |
640 KB |
Output is correct |
31 |
Correct |
4 ms |
640 KB |
Output is correct |
32 |
Correct |
6 ms |
640 KB |
Output is correct |
33 |
Correct |
5 ms |
640 KB |
Output is correct |
34 |
Correct |
3 ms |
640 KB |
Output is correct |
35 |
Correct |
5 ms |
640 KB |
Output is correct |
36 |
Correct |
6 ms |
640 KB |
Output is correct |
37 |
Correct |
2 ms |
656 KB |
Output is correct |
38 |
Correct |
2 ms |
640 KB |
Output is correct |
39 |
Correct |
2 ms |
640 KB |
Output is correct |
40 |
Correct |
268 ms |
14428 KB |
Output is correct |
41 |
Correct |
307 ms |
14804 KB |
Output is correct |
42 |
Correct |
255 ms |
14300 KB |
Output is correct |
43 |
Correct |
425 ms |
14300 KB |
Output is correct |
44 |
Correct |
222 ms |
14428 KB |
Output is correct |
45 |
Correct |
507 ms |
14096 KB |
Output is correct |
46 |
Correct |
312 ms |
14048 KB |
Output is correct |
47 |
Correct |
108 ms |
13556 KB |
Output is correct |
48 |
Correct |
117 ms |
13692 KB |
Output is correct |
49 |
Correct |
80 ms |
10184 KB |
Output is correct |
50 |
Correct |
62 ms |
9924 KB |
Output is correct |
51 |
Correct |
77 ms |
9788 KB |
Output is correct |
52 |
Correct |
783 ms |
15448 KB |
Output is correct |
53 |
Correct |
977 ms |
15832 KB |
Output is correct |
54 |
Correct |
1905 ms |
15440 KB |
Output is correct |
55 |
Correct |
685 ms |
15324 KB |
Output is correct |
56 |
Correct |
1532 ms |
15040 KB |
Output is correct |
57 |
Correct |
2168 ms |
14896 KB |
Output is correct |
58 |
Correct |
831 ms |
14940 KB |
Output is correct |
59 |
Correct |
771 ms |
11000 KB |
Output is correct |