#include<cstdio>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, m;
struct point {
int a, b;
long long c;
bool operator<(const point &p)const {
return b != p.b ? b<p.b : a>p.a;
}
}w[201000];
struct Tree {
long long Mx[SZ + SZ], K[SZ+SZ];
void init() {
int i;
for (i = 0; i < SZ + SZ; i++)Mx[i] = K[i] = 0;
}
void Add2(int nd, long long x) {
Mx[nd] += x;
K[nd] += x;
}
void Spread(int nd) {
Add2(nd * 2, K[nd]);
Add2(nd * 2 + 1, K[nd]);
K[nd] = 0;
}
void UDT(int nd) {
Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
}
void Add(int nd, int b, int e, int s, int l, long long x) {
if (s <= b && e <= l) {
Add2(nd, x);
return;
}
int m = (b + e) >> 1;
Spread(nd);
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 Max(int nd, int b, int e, int s, int l) {
if (s <= b && e <= l)return Mx[nd];
int m = (b + e) >> 1;
long long r = 0;
Spread(nd);
if (s <= m)r = max(r, Max(nd * 2, b, m, s, l));
if (l > m)r = max(r, Max(nd * 2 + 1, m + 1, e, s, l));
return r;
}
}T;
bool Pos(long long K) {
int i;
T.init();
long long s = 0;
for (i = 1; i <= m; i++) {
long long M = T.Max(1, 1, n, w[i].a, w[i].b - 1);
long long t = min(K - M, w[i].c);
s += w[i].c - t;
if (s > K)return false;
T.Add(1, 1, n, w[i].a, w[i].b - 1, t);
}
return true;
}
int main() {
int i, j;
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++) {
scanf("%d%d%lld", &w[i].a, &w[i].b, &w[i].c);
if (w[i].a > w[i].b)swap(w[i].a, w[i].b);
}
sort(w + 1, w + m + 1);
long long b = 1, e = 1e15, mid, r;
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:67: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &w[i].a, &w[i].b, &w[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
8568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
8568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
8568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
8568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
8568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
