Submission #1024074

#TimeUsernameProblemLanguageResultExecution timeMemory
1024074lucriSails (IOI07_sails)C++17
80 / 100
1079 ms5112 KiB
#include <iostream> #include <algorithm> using namespace std; unsigned int n,hmax,cost,length; unsigned long long ans; unsigned int lss,ls,h,w; pair<unsigned int,unsigned int>v[100010]; pair<unsigned int,unsigned int>tr; pair<unsigned int,unsigned int>s[100010]; pair<unsigned int,unsigned int>ss[100010]; void qsort(int b,int e) { if(b>=e) return; int bb=b,ee=e,adb=1,ade=0; while(bb<ee) { if(v[bb].first>v[ee].first) { tr=v[bb]; v[bb]=v[ee]; v[ee]=tr; adb=1-adb; ade=1-ade; } bb+=adb; ee-=ade; } qsort(b,bb-1); qsort(bb+1,e); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL)); cin>>n; for(int i=1;i<=n;++i) cin>>v[i].first>>v[i].second; swap(v[1],v[rand()%n+1]); qsort(1,n); for(int i=1;i<=n;++i) { h=v[i].first; w=v[i].second; if(h>hmax) { cost=0; length=h-hmax; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; hmax=h; } while(w) { if(w>=s[ls].second) { ss[++lss]={s[ls].first+1,s[ls].second}; ans+=1LL*s[ls].first*s[ls].second; w-=s[ls].second; --ls; } else { ans+=1LL*w*s[ls].first; ss[++lss]={s[ls].first,s[ls].second-w}; ss[++lss]={s[ls].first+1,w}; w=0; --ls; break; } } cost=ss[lss].first; length=ss[lss].second; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; --lss; if(lss) { cost=ss[lss].first; length=ss[lss].second; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; --lss; if(lss) { cost=ss[lss].first; length=ss[lss].second; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; --lss; while(lss) { s[++ls]={ss[lss].first,ss[lss].second}; --lss; } } } } cout<<ans; return 0; }

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   39 |     for(int i=1;i<=n;++i)
      |                 ~^~~
sails.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   43 |     for(int i=1;i<=n;++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...
#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...