#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, int x){
Mn[nd] += x;
K[nd] += x;
}
void Spread(int nd){
Add2(nd*2,K[nd]);
Add2(nd*2+1,K[nd]);
}
void Add(int nd, int b, int e, int s, int l, int x){
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){
int 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:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
arranging_tickets.cpp:87:10: 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:90:14: 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 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
