#include<bits/stdc++.h>
using namespace std;
int N, M, l[100009], r[100009], c[100009];
long long maxA, sumC, b[200009], a[200009], aib[200009];
vector < pair < int, int > > v[200009];
void U (int pos, int val)
{
while (pos <= N)
aib[pos] += val,
pos += pos - (pos & (pos - 1));
}
long long Q (int pos)
{
long long sum = 0;
while (pos)
sum += aib[pos],
pos &= pos - 1;
return sum;
}
bool getVerdict (long long S, long long cntFlipped)
{
if (cntFlipped > sumC) return 0;
for (int i=1; i<=N; i++)
{
long long newA = a[i] + cntFlipped;
if (newA < S) b[i] = 0;
else b[i] = (newA + 1 - S) / 2;
}
for (int i=1; i<=N; i++)
aib[i] = 0;
long long used = 0;
priority_queue < pair < int, int > > PQ;
for (int i=1; i<=N; i++)
{
for (auto r : v[i])
PQ.push (r);
long long needed = max (0LL, b[i] - Q (N - i + 1));
while (!PQ.empty ())
{
auto curr = PQ.top ();
PQ.pop ();
long long f = min (needed, (long long) curr.second);
used += f, needed -= f;
U (N - curr.first + 1, +f);
if (f != curr.second)
PQ.push ({curr.first, curr.second - f});
if (needed == 0)
break;
}
if (needed > 0) return 0;
}
return (used <= cntFlipped);
}
bool ok (long long S)
{
if (S >= maxA) return 1;
if (getVerdict (S, maxA - S)) return 1;
if (getVerdict (S, maxA - S + 1)) return 1;
return 0;
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d %d", &N, &M);
///N links: 1-2, 2-3, .., N-1
for (int i=1; i<=M; i++)
{
scanf ("%d %d %d", &l[i], &r[i], &c[i]), sumC += c[i];
if (l[i] > r[i]) swap (l[i], r[i]);
a[l[i]] += c[i], a[r[i]] -= c[i];
v[l[i]].push_back ({r[i] - 1, c[i]});
}
long long p = 1, u = 0, mij, ras;
for (int i=1; i<=N; i++)
a[i] += a[i - 1], u = max (u, a[i]);
maxA = u;
while (p <= u)
{
mij = (p + u) >> 1;
if (ok (mij)) ras = mij, u = mij - 1;
else p = mij + 1;
}
printf ("%lld\n", ras);
return 0;
}
Compilation message
arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:73: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:77:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d %d", &l[i], &r[i], &c[i]), sumC += c[i];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
5 ms |
5184 KB |
Output is correct |
5 |
Correct |
5 ms |
5184 KB |
Output is correct |
6 |
Correct |
7 ms |
5244 KB |
Output is correct |
7 |
Correct |
5 ms |
5260 KB |
Output is correct |
8 |
Correct |
7 ms |
5260 KB |
Output is correct |
9 |
Correct |
6 ms |
5260 KB |
Output is correct |
10 |
Correct |
5 ms |
5296 KB |
Output is correct |
11 |
Correct |
7 ms |
5296 KB |
Output is correct |
12 |
Correct |
5 ms |
5308 KB |
Output is correct |
13 |
Correct |
6 ms |
5308 KB |
Output is correct |
14 |
Correct |
6 ms |
5308 KB |
Output is correct |
15 |
Correct |
5 ms |
5308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
5 ms |
5184 KB |
Output is correct |
5 |
Correct |
5 ms |
5184 KB |
Output is correct |
6 |
Correct |
7 ms |
5244 KB |
Output is correct |
7 |
Correct |
5 ms |
5260 KB |
Output is correct |
8 |
Correct |
7 ms |
5260 KB |
Output is correct |
9 |
Correct |
6 ms |
5260 KB |
Output is correct |
10 |
Correct |
5 ms |
5296 KB |
Output is correct |
11 |
Correct |
7 ms |
5296 KB |
Output is correct |
12 |
Correct |
5 ms |
5308 KB |
Output is correct |
13 |
Correct |
6 ms |
5308 KB |
Output is correct |
14 |
Correct |
6 ms |
5308 KB |
Output is correct |
15 |
Correct |
5 ms |
5308 KB |
Output is correct |
16 |
Correct |
6 ms |
5308 KB |
Output is correct |
17 |
Correct |
6 ms |
5308 KB |
Output is correct |
18 |
Correct |
6 ms |
5308 KB |
Output is correct |
19 |
Correct |
6 ms |
5356 KB |
Output is correct |
20 |
Correct |
6 ms |
5356 KB |
Output is correct |
21 |
Correct |
6 ms |
5356 KB |
Output is correct |
22 |
Correct |
6 ms |
5356 KB |
Output is correct |
23 |
Correct |
6 ms |
5356 KB |
Output is correct |
24 |
Correct |
6 ms |
5356 KB |
Output is correct |
25 |
Correct |
6 ms |
5356 KB |
Output is correct |
26 |
Correct |
6 ms |
5356 KB |
Output is correct |
27 |
Correct |
6 ms |
5356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
5 ms |
5184 KB |
Output is correct |
5 |
Correct |
5 ms |
5184 KB |
Output is correct |
6 |
Correct |
7 ms |
5244 KB |
Output is correct |
7 |
Correct |
5 ms |
5260 KB |
Output is correct |
8 |
Correct |
7 ms |
5260 KB |
Output is correct |
9 |
Correct |
6 ms |
5260 KB |
Output is correct |
10 |
Correct |
5 ms |
5296 KB |
Output is correct |
11 |
Correct |
7 ms |
5296 KB |
Output is correct |
12 |
Correct |
5 ms |
5308 KB |
Output is correct |
13 |
Correct |
6 ms |
5308 KB |
Output is correct |
14 |
Correct |
6 ms |
5308 KB |
Output is correct |
15 |
Correct |
5 ms |
5308 KB |
Output is correct |
16 |
Correct |
6 ms |
5308 KB |
Output is correct |
17 |
Correct |
6 ms |
5308 KB |
Output is correct |
18 |
Correct |
6 ms |
5308 KB |
Output is correct |
19 |
Correct |
6 ms |
5356 KB |
Output is correct |
20 |
Correct |
6 ms |
5356 KB |
Output is correct |
21 |
Correct |
6 ms |
5356 KB |
Output is correct |
22 |
Correct |
6 ms |
5356 KB |
Output is correct |
23 |
Correct |
6 ms |
5356 KB |
Output is correct |
24 |
Correct |
6 ms |
5356 KB |
Output is correct |
25 |
Correct |
6 ms |
5356 KB |
Output is correct |
26 |
Correct |
6 ms |
5356 KB |
Output is correct |
27 |
Correct |
6 ms |
5356 KB |
Output is correct |
28 |
Correct |
14 ms |
5500 KB |
Output is correct |
29 |
Correct |
13 ms |
5524 KB |
Output is correct |
30 |
Correct |
13 ms |
5552 KB |
Output is correct |
31 |
Correct |
15 ms |
5552 KB |
Output is correct |
32 |
Correct |
15 ms |
5552 KB |
Output is correct |
33 |
Correct |
13 ms |
5572 KB |
Output is correct |
34 |
Correct |
8 ms |
5572 KB |
Output is correct |
35 |
Correct |
10 ms |
5572 KB |
Output is correct |
36 |
Correct |
13 ms |
5572 KB |
Output is correct |
37 |
Correct |
8 ms |
5572 KB |
Output is correct |
38 |
Correct |
8 ms |
5572 KB |
Output is correct |
39 |
Correct |
8 ms |
5572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
5 ms |
5184 KB |
Output is correct |
5 |
Correct |
5 ms |
5184 KB |
Output is correct |
6 |
Correct |
7 ms |
5244 KB |
Output is correct |
7 |
Correct |
5 ms |
5260 KB |
Output is correct |
8 |
Correct |
7 ms |
5260 KB |
Output is correct |
9 |
Correct |
6 ms |
5260 KB |
Output is correct |
10 |
Correct |
5 ms |
5296 KB |
Output is correct |
11 |
Correct |
7 ms |
5296 KB |
Output is correct |
12 |
Correct |
5 ms |
5308 KB |
Output is correct |
13 |
Correct |
6 ms |
5308 KB |
Output is correct |
14 |
Correct |
6 ms |
5308 KB |
Output is correct |
15 |
Correct |
5 ms |
5308 KB |
Output is correct |
16 |
Correct |
6 ms |
5308 KB |
Output is correct |
17 |
Correct |
6 ms |
5308 KB |
Output is correct |
18 |
Correct |
6 ms |
5308 KB |
Output is correct |
19 |
Correct |
6 ms |
5356 KB |
Output is correct |
20 |
Correct |
6 ms |
5356 KB |
Output is correct |
21 |
Correct |
6 ms |
5356 KB |
Output is correct |
22 |
Correct |
6 ms |
5356 KB |
Output is correct |
23 |
Correct |
6 ms |
5356 KB |
Output is correct |
24 |
Correct |
6 ms |
5356 KB |
Output is correct |
25 |
Correct |
6 ms |
5356 KB |
Output is correct |
26 |
Correct |
6 ms |
5356 KB |
Output is correct |
27 |
Correct |
6 ms |
5356 KB |
Output is correct |
28 |
Correct |
14 ms |
5500 KB |
Output is correct |
29 |
Correct |
13 ms |
5524 KB |
Output is correct |
30 |
Correct |
13 ms |
5552 KB |
Output is correct |
31 |
Correct |
15 ms |
5552 KB |
Output is correct |
32 |
Correct |
15 ms |
5552 KB |
Output is correct |
33 |
Correct |
13 ms |
5572 KB |
Output is correct |
34 |
Correct |
8 ms |
5572 KB |
Output is correct |
35 |
Correct |
10 ms |
5572 KB |
Output is correct |
36 |
Correct |
13 ms |
5572 KB |
Output is correct |
37 |
Correct |
8 ms |
5572 KB |
Output is correct |
38 |
Correct |
8 ms |
5572 KB |
Output is correct |
39 |
Correct |
8 ms |
5572 KB |
Output is correct |
40 |
Correct |
881 ms |
14920 KB |
Output is correct |
41 |
Correct |
907 ms |
15128 KB |
Output is correct |
42 |
Correct |
155 ms |
15128 KB |
Output is correct |
43 |
Correct |
1002 ms |
15128 KB |
Output is correct |
44 |
Correct |
1171 ms |
15128 KB |
Output is correct |
45 |
Correct |
1234 ms |
15128 KB |
Output is correct |
46 |
Correct |
200 ms |
15128 KB |
Output is correct |
47 |
Correct |
139 ms |
15128 KB |
Output is correct |
48 |
Correct |
194 ms |
15128 KB |
Output is correct |
49 |
Correct |
125 ms |
15128 KB |
Output is correct |
50 |
Correct |
309 ms |
15128 KB |
Output is correct |
51 |
Correct |
132 ms |
15128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
5 ms |
5184 KB |
Output is correct |
5 |
Correct |
5 ms |
5184 KB |
Output is correct |
6 |
Correct |
7 ms |
5244 KB |
Output is correct |
7 |
Correct |
5 ms |
5260 KB |
Output is correct |
8 |
Correct |
7 ms |
5260 KB |
Output is correct |
9 |
Correct |
6 ms |
5260 KB |
Output is correct |
10 |
Correct |
5 ms |
5296 KB |
Output is correct |
11 |
Correct |
7 ms |
5296 KB |
Output is correct |
12 |
Correct |
5 ms |
5308 KB |
Output is correct |
13 |
Correct |
6 ms |
5308 KB |
Output is correct |
14 |
Correct |
6 ms |
5308 KB |
Output is correct |
15 |
Correct |
5 ms |
5308 KB |
Output is correct |
16 |
Correct |
6 ms |
5308 KB |
Output is correct |
17 |
Correct |
6 ms |
5308 KB |
Output is correct |
18 |
Correct |
6 ms |
5308 KB |
Output is correct |
19 |
Correct |
6 ms |
5356 KB |
Output is correct |
20 |
Correct |
6 ms |
5356 KB |
Output is correct |
21 |
Correct |
6 ms |
5356 KB |
Output is correct |
22 |
Correct |
6 ms |
5356 KB |
Output is correct |
23 |
Correct |
6 ms |
5356 KB |
Output is correct |
24 |
Correct |
6 ms |
5356 KB |
Output is correct |
25 |
Correct |
6 ms |
5356 KB |
Output is correct |
26 |
Correct |
6 ms |
5356 KB |
Output is correct |
27 |
Correct |
6 ms |
5356 KB |
Output is correct |
28 |
Correct |
14 ms |
5500 KB |
Output is correct |
29 |
Correct |
13 ms |
5524 KB |
Output is correct |
30 |
Correct |
13 ms |
5552 KB |
Output is correct |
31 |
Correct |
15 ms |
5552 KB |
Output is correct |
32 |
Correct |
15 ms |
5552 KB |
Output is correct |
33 |
Correct |
13 ms |
5572 KB |
Output is correct |
34 |
Correct |
8 ms |
5572 KB |
Output is correct |
35 |
Correct |
10 ms |
5572 KB |
Output is correct |
36 |
Correct |
13 ms |
5572 KB |
Output is correct |
37 |
Correct |
8 ms |
5572 KB |
Output is correct |
38 |
Correct |
8 ms |
5572 KB |
Output is correct |
39 |
Correct |
8 ms |
5572 KB |
Output is correct |
40 |
Correct |
881 ms |
14920 KB |
Output is correct |
41 |
Correct |
907 ms |
15128 KB |
Output is correct |
42 |
Correct |
155 ms |
15128 KB |
Output is correct |
43 |
Correct |
1002 ms |
15128 KB |
Output is correct |
44 |
Correct |
1171 ms |
15128 KB |
Output is correct |
45 |
Correct |
1234 ms |
15128 KB |
Output is correct |
46 |
Correct |
200 ms |
15128 KB |
Output is correct |
47 |
Correct |
139 ms |
15128 KB |
Output is correct |
48 |
Correct |
194 ms |
15128 KB |
Output is correct |
49 |
Correct |
125 ms |
15128 KB |
Output is correct |
50 |
Correct |
309 ms |
15128 KB |
Output is correct |
51 |
Correct |
132 ms |
15128 KB |
Output is correct |
52 |
Correct |
3442 ms |
15156 KB |
Output is correct |
53 |
Correct |
174 ms |
15156 KB |
Output is correct |
54 |
Correct |
3192 ms |
15156 KB |
Output is correct |
55 |
Correct |
3405 ms |
15156 KB |
Output is correct |
56 |
Correct |
3114 ms |
15156 KB |
Output is correct |
57 |
Correct |
3387 ms |
15156 KB |
Output is correct |
58 |
Correct |
2800 ms |
15156 KB |
Output is correct |
59 |
Correct |
1540 ms |
15156 KB |
Output is correct |