#include<cstdio>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, m;
struct point {
int a, b, c;
bool operator <(point &p)const {
return a < p.a;
}
}w[201000];
long long S[201000], Z[201000], H[201000];
struct Tree {
long long Mn[SZ + SZ], K[SZ + SZ];
void UDT(int nd) {
Mn[nd] = min(Mn[nd * 2], Mn[nd * 2 + 1]);
}
void init(int nd, int b, int e) {
K[nd] = 0;
if (b == e) {
Mn[nd] = H[b];
return;
}
int m = (b + e) >> 1;
init(nd * 2, b, m);
init(nd * 2 + 1, m + 1, e);
UDT(nd);
}
void Add2(int nd, long long x) {
Mn[nd] += x;
K[nd] += x;
}
void Spread(int nd) {
Add2(nd * 2, K[nd]);
Add2(nd * 2 + 1, K[nd]);
K[nd] = 0;
}
void Add(int nd, int b, int e, int s, int l, long long x) {
if (s > l)return;
if (s <= b && e <= l) {
Add2(nd, x);
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (s <= m)Add(nd * 2, b, m, s, l, x);
if (l > m)Add(nd * 2 + 1, m + 1, e, s, l, x);
UDT(nd);
}
long long Min(int nd, int b, int e, int s, int l) {
if (s > l)return (long long)1e18;
if (s <= b && e <= l)return Mn[nd];
Spread(nd);
int m = (b + e) >> 1;
long long r = 1e18;
if (s <= m)r = min(Min(nd * 2, b, m, s, l), r);
if (l > m)r = min(Min(nd * 2 + 1, m + 1, e, s, l), r);
return r;
}
}T;
int pv;
long long Get() {
int i;
T.init(1, 0, n - 1);
long long res = 0;
for (i = 1; i <= m; i++) {
long long t = min(min(T.Min(1, 0, n - 1, 0, w[i].a - 1), T.Min(1, 0, n - 1, w[i].b, n - 1)), (long long)w[i].c);
res += t;
T.Add(1, 0, n - 1, 0, w[i].a - 1, -t);
T.Add(1, 0, n - 1, w[i].b, n - 1, -t);
}
return res;
}
bool Pos(long long M) {
long long i, j;
long long bb = Z[pv] - M, ee = M / 2;
for (i = bb; i <= bb + 1; i++) {
for (j = 0; j < n; j++) {
H[j] = (i + M - Z[j]) / 2;
}
if (H[0] < i)continue;
if (Get() >= i)return true;
}
return false;
}
int main() {
int i;
//freopen("input.txt","r",stdin);
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (a > b)swap(a, b);
w[i] = { a,b,c };
S[a] += c;
S[b] -= c;
}
sort(w + 1, w + m + 1);
long long Mx = -1;
pv = -1;
for (i = 1; i < n; i++) {
S[i] += S[i - 1];
if (Mx < S[i]) {
Mx = S[i];
pv = i;
}
}
for (i = 1; i <= pv; i++)Z[i] = max(Z[i - 1], S[i]);
for (i = n - 1; i >= pv; i--)Z[i] = max(Z[i + 1], S[i]);
long long b = 0, e = Mx - 1, mid, r = Mx;
while (b <= e) {
mid = (b + e) >> 1;
if (Pos(mid)) {
r = mid;
e = mid - 1;
}
else b = mid + 1;
}
printf("%lld\n", r);
}
Compilation message
arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:89:7: 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:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
4 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
4 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
20 ms |
632 KB |
Output is correct |
29 |
Correct |
20 ms |
632 KB |
Output is correct |
30 |
Correct |
22 ms |
632 KB |
Output is correct |
31 |
Correct |
22 ms |
632 KB |
Output is correct |
32 |
Correct |
23 ms |
632 KB |
Output is correct |
33 |
Correct |
21 ms |
632 KB |
Output is correct |
34 |
Correct |
19 ms |
632 KB |
Output is correct |
35 |
Correct |
20 ms |
632 KB |
Output is correct |
36 |
Correct |
21 ms |
632 KB |
Output is correct |
37 |
Correct |
19 ms |
632 KB |
Output is correct |
38 |
Correct |
11 ms |
632 KB |
Output is correct |
39 |
Correct |
16 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
4 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
20 ms |
632 KB |
Output is correct |
29 |
Correct |
20 ms |
632 KB |
Output is correct |
30 |
Correct |
22 ms |
632 KB |
Output is correct |
31 |
Correct |
22 ms |
632 KB |
Output is correct |
32 |
Correct |
23 ms |
632 KB |
Output is correct |
33 |
Correct |
21 ms |
632 KB |
Output is correct |
34 |
Correct |
19 ms |
632 KB |
Output is correct |
35 |
Correct |
20 ms |
632 KB |
Output is correct |
36 |
Correct |
21 ms |
632 KB |
Output is correct |
37 |
Correct |
19 ms |
632 KB |
Output is correct |
38 |
Correct |
11 ms |
632 KB |
Output is correct |
39 |
Correct |
16 ms |
632 KB |
Output is correct |
40 |
Correct |
1748 ms |
14556 KB |
Output is correct |
41 |
Correct |
1637 ms |
14532 KB |
Output is correct |
42 |
Correct |
1679 ms |
14556 KB |
Output is correct |
43 |
Correct |
2123 ms |
14584 KB |
Output is correct |
44 |
Correct |
2367 ms |
14524 KB |
Output is correct |
45 |
Correct |
2539 ms |
14456 KB |
Output is correct |
46 |
Correct |
1481 ms |
14584 KB |
Output is correct |
47 |
Correct |
1470 ms |
14584 KB |
Output is correct |
48 |
Correct |
1499 ms |
14456 KB |
Output is correct |
49 |
Correct |
1254 ms |
8056 KB |
Output is correct |
50 |
Correct |
1002 ms |
8128 KB |
Output is correct |
51 |
Correct |
1164 ms |
8188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
4 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
20 ms |
632 KB |
Output is correct |
29 |
Correct |
20 ms |
632 KB |
Output is correct |
30 |
Correct |
22 ms |
632 KB |
Output is correct |
31 |
Correct |
22 ms |
632 KB |
Output is correct |
32 |
Correct |
23 ms |
632 KB |
Output is correct |
33 |
Correct |
21 ms |
632 KB |
Output is correct |
34 |
Correct |
19 ms |
632 KB |
Output is correct |
35 |
Correct |
20 ms |
632 KB |
Output is correct |
36 |
Correct |
21 ms |
632 KB |
Output is correct |
37 |
Correct |
19 ms |
632 KB |
Output is correct |
38 |
Correct |
11 ms |
632 KB |
Output is correct |
39 |
Correct |
16 ms |
632 KB |
Output is correct |
40 |
Correct |
1748 ms |
14556 KB |
Output is correct |
41 |
Correct |
1637 ms |
14532 KB |
Output is correct |
42 |
Correct |
1679 ms |
14556 KB |
Output is correct |
43 |
Correct |
2123 ms |
14584 KB |
Output is correct |
44 |
Correct |
2367 ms |
14524 KB |
Output is correct |
45 |
Correct |
2539 ms |
14456 KB |
Output is correct |
46 |
Correct |
1481 ms |
14584 KB |
Output is correct |
47 |
Correct |
1470 ms |
14584 KB |
Output is correct |
48 |
Correct |
1499 ms |
14456 KB |
Output is correct |
49 |
Correct |
1254 ms |
8056 KB |
Output is correct |
50 |
Correct |
1002 ms |
8128 KB |
Output is correct |
51 |
Correct |
1164 ms |
8188 KB |
Output is correct |
52 |
Execution timed out |
6087 ms |
14504 KB |
Time limit exceeded |
53 |
Halted |
0 ms |
0 KB |
- |