#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (200005)
#define MAXM (100005)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
struct Node {
Node(int s, int e, int c) : s(s), e(e), c(c) {}
int s, e, c;
bool operator < (const Node& t) const {
if(e != t.e) return e > t.e;
if(s != t.s) return s < t.s;
return c > t.c;
}
bool operator > (const Node& t) const { return !operator <(t); }
};
priority_queue<Node, vector<Node>, greater<Node>> PQ;
vector<pii> G[MAXN]; // {e, c}
vector<piii> L, RL;
ll S[MAXN], Q[MAXN], V[MAXN];
int d[MAXN];
int A[MAXM], B[MAXM], C[MAXM];
int N, M;
ll Ans;
bool f(ll m, ll n, int x) {
while(!PQ.empty()) PQ.pop();
for(int i = 0; i <= x; i++) clv(G[i]);
clv(RL);
for(piii& l : L) {
int s, e; tie(s, e) = l.first;
if(x < s || e < x) continue;
G[s].pb({e, l.second});
}
for(int i = 0; i < x; i++) Q[i] = (S[i] + n - m + 1) / 2;
Q[x] = n;
ll cnt = 0;
for(int i = 0; i <= x; i++) {
for(pii& v : G[i]) PQ.push(Node(i, v.first, v.second));
while(cnt < Q[i]) {
if(PQ.empty()) return false;
Node ret = PQ.top(); PQ.pop();
if(cnt+ret.c <= Q[i]) {
RL.pb({{ret.s, ret.e}, ret.c});
cnt += ret.c;
} else {
RL.pb({{ret.s, ret.e}, Q[i] - cnt});
ll left = ret.c - Q[i] + cnt;
PQ.push(Node(ret.s, ret.e, left));
cnt = Q[i];
}
}
}
fill(V, V+N+1, 0);
for(piii& l : L) {
V[l.first.first] += l.second;
V[l.first.second+1] -= l.second;
}
for(piii& l : RL) {
int s, e, c; tie(s, e) = l.first; c = l.second;
V[s] -= c; V[e+1] += c;
if(s) { V[0] += c; V[s] -= c; }
if(e+1 < N) { V[e+1] += c; V[N] -= c; }
}
for(int i = 1; i <= N; i++) V[i] += V[i-1];
return (*max_element(V, V+N)) <= m;
}
bool f(vector<int>& VX, ll m) {
for(int x : VX) {
if(f(m, max(0ll, S[x]-m), x)) return true;
if(f(m, max(0ll, S[x]-m+1), x)) return true;
}
return false;
}
ll getAns() {
vector<int> VX;
ll s = 1, e = *max_element(S, S+N);
for(int i = 0; i < N; i++) if(e == S[i]) VX.pb(i);
{
vector<int> tmp;
tmp.pb(VX[0]); tmp.pb(VX.back());
sorv(tmp); univ(tmp);
swap(VX, tmp);
}
for(ll m; s < e;) {
m = (s+e)/2;
if(f(VX, m)) e = m; else s = m+1;
}
return s;
}
int main() {
scanf("%d%d", &N, &M);
for(int i = 0; i < M; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
for(int i = 0; i < M; i++) { A[i]--; B[i]--; }
for(int i = 0; i < M; i++) {
if(A[i] < B[i]) L.pb({{A[i], B[i]-1}, C[i]});
else L.pb({{B[i], A[i]-1}, C[i]});
}
for(piii& l : L) {
S[l.first.first] += l.second;
S[l.first.second+1] -= l.second;
}
for(int i = 1; i <= N; i++) S[i] += S[i-1];
printf("%lld\n", getAns());
return 0;
}
Compilation message
arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:106: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:107:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < M; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
8 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5084 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
8 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5084 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
4984 KB |
Output is correct |
16 |
Correct |
8 ms |
5240 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
8 ms |
5112 KB |
Output is correct |
19 |
Correct |
7 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5112 KB |
Output is correct |
22 |
Correct |
7 ms |
5112 KB |
Output is correct |
23 |
Correct |
7 ms |
5112 KB |
Output is correct |
24 |
Correct |
7 ms |
5240 KB |
Output is correct |
25 |
Correct |
7 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5116 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
8 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5084 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
4984 KB |
Output is correct |
16 |
Correct |
8 ms |
5240 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
8 ms |
5112 KB |
Output is correct |
19 |
Correct |
7 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5112 KB |
Output is correct |
22 |
Correct |
7 ms |
5112 KB |
Output is correct |
23 |
Correct |
7 ms |
5112 KB |
Output is correct |
24 |
Correct |
7 ms |
5240 KB |
Output is correct |
25 |
Correct |
7 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5116 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
28 |
Correct |
12 ms |
5368 KB |
Output is correct |
29 |
Correct |
12 ms |
5368 KB |
Output is correct |
30 |
Correct |
12 ms |
5368 KB |
Output is correct |
31 |
Correct |
11 ms |
5368 KB |
Output is correct |
32 |
Correct |
13 ms |
5368 KB |
Output is correct |
33 |
Correct |
13 ms |
5496 KB |
Output is correct |
34 |
Correct |
12 ms |
5368 KB |
Output is correct |
35 |
Correct |
11 ms |
5368 KB |
Output is correct |
36 |
Correct |
16 ms |
5368 KB |
Output is correct |
37 |
Correct |
11 ms |
5368 KB |
Output is correct |
38 |
Correct |
9 ms |
5368 KB |
Output is correct |
39 |
Correct |
9 ms |
5240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
8 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5084 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
4984 KB |
Output is correct |
16 |
Correct |
8 ms |
5240 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
8 ms |
5112 KB |
Output is correct |
19 |
Correct |
7 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5112 KB |
Output is correct |
22 |
Correct |
7 ms |
5112 KB |
Output is correct |
23 |
Correct |
7 ms |
5112 KB |
Output is correct |
24 |
Correct |
7 ms |
5240 KB |
Output is correct |
25 |
Correct |
7 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5116 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
28 |
Correct |
12 ms |
5368 KB |
Output is correct |
29 |
Correct |
12 ms |
5368 KB |
Output is correct |
30 |
Correct |
12 ms |
5368 KB |
Output is correct |
31 |
Correct |
11 ms |
5368 KB |
Output is correct |
32 |
Correct |
13 ms |
5368 KB |
Output is correct |
33 |
Correct |
13 ms |
5496 KB |
Output is correct |
34 |
Correct |
12 ms |
5368 KB |
Output is correct |
35 |
Correct |
11 ms |
5368 KB |
Output is correct |
36 |
Correct |
16 ms |
5368 KB |
Output is correct |
37 |
Correct |
11 ms |
5368 KB |
Output is correct |
38 |
Correct |
9 ms |
5368 KB |
Output is correct |
39 |
Correct |
9 ms |
5240 KB |
Output is correct |
40 |
Correct |
468 ms |
16372 KB |
Output is correct |
41 |
Correct |
486 ms |
16872 KB |
Output is correct |
42 |
Correct |
251 ms |
15976 KB |
Output is correct |
43 |
Correct |
564 ms |
16236 KB |
Output is correct |
44 |
Correct |
387 ms |
16488 KB |
Output is correct |
45 |
Correct |
547 ms |
15732 KB |
Output is correct |
46 |
Correct |
293 ms |
15980 KB |
Output is correct |
47 |
Correct |
253 ms |
16488 KB |
Output is correct |
48 |
Correct |
279 ms |
15336 KB |
Output is correct |
49 |
Correct |
247 ms |
14224 KB |
Output is correct |
50 |
Correct |
80 ms |
12032 KB |
Output is correct |
51 |
Correct |
196 ms |
13420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
7 ms |
5088 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
8 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5084 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
4984 KB |
Output is correct |
16 |
Correct |
8 ms |
5240 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
8 ms |
5112 KB |
Output is correct |
19 |
Correct |
7 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5112 KB |
Output is correct |
22 |
Correct |
7 ms |
5112 KB |
Output is correct |
23 |
Correct |
7 ms |
5112 KB |
Output is correct |
24 |
Correct |
7 ms |
5240 KB |
Output is correct |
25 |
Correct |
7 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5116 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
28 |
Correct |
12 ms |
5368 KB |
Output is correct |
29 |
Correct |
12 ms |
5368 KB |
Output is correct |
30 |
Correct |
12 ms |
5368 KB |
Output is correct |
31 |
Correct |
11 ms |
5368 KB |
Output is correct |
32 |
Correct |
13 ms |
5368 KB |
Output is correct |
33 |
Correct |
13 ms |
5496 KB |
Output is correct |
34 |
Correct |
12 ms |
5368 KB |
Output is correct |
35 |
Correct |
11 ms |
5368 KB |
Output is correct |
36 |
Correct |
16 ms |
5368 KB |
Output is correct |
37 |
Correct |
11 ms |
5368 KB |
Output is correct |
38 |
Correct |
9 ms |
5368 KB |
Output is correct |
39 |
Correct |
9 ms |
5240 KB |
Output is correct |
40 |
Correct |
468 ms |
16372 KB |
Output is correct |
41 |
Correct |
486 ms |
16872 KB |
Output is correct |
42 |
Correct |
251 ms |
15976 KB |
Output is correct |
43 |
Correct |
564 ms |
16236 KB |
Output is correct |
44 |
Correct |
387 ms |
16488 KB |
Output is correct |
45 |
Correct |
547 ms |
15732 KB |
Output is correct |
46 |
Correct |
293 ms |
15980 KB |
Output is correct |
47 |
Correct |
253 ms |
16488 KB |
Output is correct |
48 |
Correct |
279 ms |
15336 KB |
Output is correct |
49 |
Correct |
247 ms |
14224 KB |
Output is correct |
50 |
Correct |
80 ms |
12032 KB |
Output is correct |
51 |
Correct |
196 ms |
13420 KB |
Output is correct |
52 |
Correct |
1225 ms |
19616 KB |
Output is correct |
53 |
Correct |
349 ms |
17512 KB |
Output is correct |
54 |
Correct |
3362 ms |
18796 KB |
Output is correct |
55 |
Correct |
996 ms |
18964 KB |
Output is correct |
56 |
Correct |
1686 ms |
17768 KB |
Output is correct |
57 |
Correct |
2301 ms |
17612 KB |
Output is correct |
58 |
Correct |
1411 ms |
18900 KB |
Output is correct |
59 |
Correct |
1659 ms |
14832 KB |
Output is correct |