#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define pary(a...) danb(#a, a)
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
int cnt = sizeof...(T);
((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
std::cerr << "\033[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
std::cerr << (f++ ? ", " : "") << *L;
std::cerr << " ]\033[0m\n";
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back
#define get_pos(u,x) int(lower_bound(all(u),x)-begin(u))
using namespace std;
using ll = int_fast64_t;
using ld = long double;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using max_heap = priority_queue<T, vector<T>, less<T>>;
const int inf = 1e9;
const int mod = 1000000007;
const ll INF = 1e18;
const int maxn = 5002;
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
vector<tuple<int,int,int>> seg;
for (int i = 0; i < m; i++) {
int l, r, c;
cin >> l >> r >> c;
if (l > r) swap(l, r);
--l, --r;
seg.pb(l, r, c);
}
vector<ll> pref(n);
for (auto [l, r, c]: seg)
pref[l] += c, pref[r] -= c;
for (int i = 1; i < n; i++) pref[i] += pref[i-1];
sort(all(seg));
auto calc = [&](ll x) {
vector<ll> need(n);
for (int i = 0; i < n; i++)
need[i] = max<ll>(0, (pref[i] - x + 1) / 2);
ll cnt = 0;
ll sum = 0;
max_heap<pair<int,int>> pq;
vector<ll> cover(n);
for (int i = 0, it = 0; i < n; i++) {
while (it < seg.size() && get<0>(seg[it]) <= i) {
auto [l, r, c] = seg[it];
pq.emplace(r, c);
it++;
}
sum -= cover[i];
while (sum < need[i]) {
assert (!pq.empty());
auto [r, c] = pq.top(); pq.pop();
assert (r > i);
if (sum + c < need[i]) {
cover[r] += c;
sum += c;
cnt += c;
} else {
int take = need[i] - sum;
pq.emplace(r, c - take);
cover[r] += take;
sum += take;
cnt += take;
}
}
}
return x + cnt;
};
ll p0 = 0;
ll p1 = 1;
for (ll s = 1LL << 40; s > 1; s >>= 1) {
if (calc(p0 + s - 2) > calc(p0 + s))
p0 += s;
if (calc(p1 + s - 2) > calc(p1 + s))
p1 += s;
}
cout << min(calc(p0), calc(p1)) << '\n';
}
Compilation message
arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:50:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | for (auto [l, r, c]: seg)
| ^
arranging_tickets.cpp: In lambda function:
arranging_tickets.cpp:66:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | auto [l, r, c] = seg[it];
| ^
arranging_tickets.cpp:73:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
73 | auto [r, c] = pq.top(); pq.pop();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
248 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
248 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
248 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
23 ms |
492 KB |
Output is correct |
29 |
Correct |
23 ms |
492 KB |
Output is correct |
30 |
Correct |
21 ms |
496 KB |
Output is correct |
31 |
Correct |
24 ms |
492 KB |
Output is correct |
32 |
Correct |
19 ms |
492 KB |
Output is correct |
33 |
Correct |
23 ms |
496 KB |
Output is correct |
34 |
Correct |
22 ms |
484 KB |
Output is correct |
35 |
Correct |
19 ms |
500 KB |
Output is correct |
36 |
Correct |
22 ms |
488 KB |
Output is correct |
37 |
Correct |
16 ms |
460 KB |
Output is correct |
38 |
Correct |
12 ms |
588 KB |
Output is correct |
39 |
Correct |
12 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
248 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
23 ms |
492 KB |
Output is correct |
29 |
Correct |
23 ms |
492 KB |
Output is correct |
30 |
Correct |
21 ms |
496 KB |
Output is correct |
31 |
Correct |
24 ms |
492 KB |
Output is correct |
32 |
Correct |
19 ms |
492 KB |
Output is correct |
33 |
Correct |
23 ms |
496 KB |
Output is correct |
34 |
Correct |
22 ms |
484 KB |
Output is correct |
35 |
Correct |
19 ms |
500 KB |
Output is correct |
36 |
Correct |
22 ms |
488 KB |
Output is correct |
37 |
Correct |
16 ms |
460 KB |
Output is correct |
38 |
Correct |
12 ms |
588 KB |
Output is correct |
39 |
Correct |
12 ms |
460 KB |
Output is correct |
40 |
Correct |
1461 ms |
8036 KB |
Output is correct |
41 |
Correct |
1534 ms |
8156 KB |
Output is correct |
42 |
Correct |
1386 ms |
8020 KB |
Output is correct |
43 |
Correct |
1389 ms |
8044 KB |
Output is correct |
44 |
Correct |
1426 ms |
8132 KB |
Output is correct |
45 |
Correct |
1310 ms |
8036 KB |
Output is correct |
46 |
Correct |
1404 ms |
7876 KB |
Output is correct |
47 |
Correct |
1473 ms |
7992 KB |
Output is correct |
48 |
Correct |
1328 ms |
7960 KB |
Output is correct |
49 |
Correct |
779 ms |
5792 KB |
Output is correct |
50 |
Correct |
526 ms |
5744 KB |
Output is correct |
51 |
Correct |
700 ms |
5772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
248 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
23 ms |
492 KB |
Output is correct |
29 |
Correct |
23 ms |
492 KB |
Output is correct |
30 |
Correct |
21 ms |
496 KB |
Output is correct |
31 |
Correct |
24 ms |
492 KB |
Output is correct |
32 |
Correct |
19 ms |
492 KB |
Output is correct |
33 |
Correct |
23 ms |
496 KB |
Output is correct |
34 |
Correct |
22 ms |
484 KB |
Output is correct |
35 |
Correct |
19 ms |
500 KB |
Output is correct |
36 |
Correct |
22 ms |
488 KB |
Output is correct |
37 |
Correct |
16 ms |
460 KB |
Output is correct |
38 |
Correct |
12 ms |
588 KB |
Output is correct |
39 |
Correct |
12 ms |
460 KB |
Output is correct |
40 |
Correct |
1461 ms |
8036 KB |
Output is correct |
41 |
Correct |
1534 ms |
8156 KB |
Output is correct |
42 |
Correct |
1386 ms |
8020 KB |
Output is correct |
43 |
Correct |
1389 ms |
8044 KB |
Output is correct |
44 |
Correct |
1426 ms |
8132 KB |
Output is correct |
45 |
Correct |
1310 ms |
8036 KB |
Output is correct |
46 |
Correct |
1404 ms |
7876 KB |
Output is correct |
47 |
Correct |
1473 ms |
7992 KB |
Output is correct |
48 |
Correct |
1328 ms |
7960 KB |
Output is correct |
49 |
Correct |
779 ms |
5792 KB |
Output is correct |
50 |
Correct |
526 ms |
5744 KB |
Output is correct |
51 |
Correct |
700 ms |
5772 KB |
Output is correct |
52 |
Correct |
2653 ms |
7180 KB |
Output is correct |
53 |
Correct |
2398 ms |
7148 KB |
Output is correct |
54 |
Correct |
2521 ms |
7248 KB |
Output is correct |
55 |
Correct |
2529 ms |
7492 KB |
Output is correct |
56 |
Correct |
2266 ms |
7388 KB |
Output is correct |
57 |
Correct |
2387 ms |
7224 KB |
Output is correct |
58 |
Correct |
2536 ms |
7236 KB |
Output is correct |
59 |
Correct |
1326 ms |
5788 KB |
Output is correct |