Submission #113413

#TimeUsernameProblemLanguageResultExecution timeMemory
113413TadijaSebezSails (IOI07_sails)C++11
100 / 100
33 ms2232 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=100050; ll sum[N],cnt[N]; ll suf[N]; int main() { int n,h,k,mxh=0; scanf("%i",&n); for(int i=1;i<=n;i++) { scanf("%i %i",&h,&k); cnt[h]++; sum[h-k+1]++; sum[h+1]--; mxh=max(mxh,h); } for(int i=1;i<=mxh;i++) sum[i]+=sum[i-1]; stack<pair<int,int>> stk; auto push_stk=[&](int x, int sz) { if(stk.empty() || stk.top().first!=x) stk.push({x,sz}); else { pair<int,int> p=stk.top(); stk.pop(); sz+=p.second; stk.push({x,sz}); } }; push_stk(N,0); for(int i=1;i<=mxh;i++) { while(stk.size() && stk.top().first<sum[i]) { pair<int,int> p=stk.top(); stk.pop(); ll dif=1e9,nh=1e9; if(stk.size()) dif=stk.top().first-p.first,nh=stk.top().first; dif*=p.second; if(sum[i]-dif<nh) { int sz=p.second; ll lo=(sum[i]+(ll)p.first*sz)/(sz+1)-p.first; sum[i]-=lo*sz; p.first+=lo; int ost=sum[i]-p.first; sum[i]-=ost; if(ost>0) push_stk(p.first+1,ost); if(ost!=sz) push_stk(p.first,sz-ost); } else { sum[i]-=dif; push_stk(nh,p.second); } } push_stk(sum[i],1); } ll ans=0; while(stk.size()) { pair<int,int> p=stk.top(); stk.pop(); ans+=(ll)p.first*(p.first-1)/2*p.second; } printf("%lld\n",ans); return 0; }

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
sails.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&h,&k);
   ~~~~~^~~~~~~~~~~~~~~
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...