# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
113412 | 2019-05-25T12:46:32 Z | TadijaSebez | Sails (IOI07_sails) | C++11 | 1000 ms | 2296 KB |
#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]+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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 8 ms | 1792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 768 KB | Output is correct |
2 | Correct | 7 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 1252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1063 ms | 1152 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 2296 KB | Output is correct |
2 | Correct | 18 ms | 1024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 1980 KB | Output is correct |
2 | Correct | 18 ms | 640 KB | Output is correct |