Submission #99323

#TimeUsernameProblemLanguageResultExecution timeMemory
99323TadijaSebezArranging Tickets (JOI17_arranging_tickets)C++11
100 / 100
2001 ms13792 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=200050; int n,m,a[N],b[N],c[N]; int heap[N],tsz; void Push(int x) { ++tsz;int i; for(i=tsz;i>1 && b[x]>b[heap[i>>1]];i>>=1) heap[i]=heap[i>>1]; heap[i]=x; } void Pop() { int tmp=heap[tsz--],i,j; for(i=1;i*2<=tsz;i=j) { j=i*2; if(j!=tsz && b[heap[j+1]]>b[heap[j]]) j++; if(b[heap[j]]>b[tmp]) heap[i]=heap[j]; else break; } heap[i]=tmp; } ll sum[N],need[N],add[N],ost[N]; vector<int> ids[N]; bool Check(ll mid, int pos, ll flip) { for(int i=1;i<=n;i++) add[i]=0; for(int i=1;i<pos;i++) need[i]=(sum[i]+flip-mid+1)/2; need[pos]=flip; tsz=0; ll done=0; for(int i=1;i<=pos;i++) { for(int j:ids[i]) if(a[j]<=pos && pos<b[j]) Push(j),ost[j]=c[j]; while(tsz && done<need[i]) { int j=heap[1]; ll work=min(ost[j],need[i]-done); done+=work; ost[j]-=work; add[1]+=work; add[a[j]]-=2*work; add[b[j]]+=2*work; if(!ost[j]) Pop(); } if(done<need[i]) return 0; } for(int i=1;i<=n;i++) { add[i]+=add[i-1]; if(add[i]+sum[i]>mid) return 0; } return 1; } int main() { scanf("%i %i",&n,&m); for(int i=1;i<=m;i++) { scanf("%i %i %i",&a[i],&b[i],&c[i]); if(a[i]>b[i]) swap(a[i],b[i]); sum[a[i]]+=c[i]; sum[b[i]]-=c[i]; ids[a[i]].push_back(i); } int fir=0,las=0; for(int i=1;i<=n;i++) { sum[i]+=sum[i-1]; if(sum[i]>sum[fir]) fir=i; if(sum[i]==sum[fir]) las=i; } ll top=sum[fir],bot=0,mid,ans=top; while(top>=bot) { mid=top+bot>>1; if(Check(mid,fir,sum[fir]-mid)||Check(mid,fir,sum[fir]-mid+1) ||Check(mid,las,sum[las]-mid)||Check(mid,las,sum[las]-mid+1)) ans=mid,top=mid-1; else bot=mid+1; } printf("%lld\n",ans); return 0; }

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
arranging_tickets.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&a[i],&b[i],&c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...