#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] -= l.second;
}
for(piii& l : RL) {
int s, e, c; tie(s, e) = l.first; c = l.second;
V[s] -= c; V[e] += 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(ll m) {
for(int x = 0; x < N; x++) {
for(ll n = 0; n <= max(0ll, S[x]-m+1); n++) {
if(f(m, n, x)) return true;
}
}
return false;
}
ll getAns() {
ll s = 1, e = *max_element(S, S+N); for(ll m; s < e;) {
m = (s+e)/2;
if(f(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:98:23: 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:99:65: 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 |
Incorrect |
0 ms |
13352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
13352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
13352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
13352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
13352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
