이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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>s[100010];
pair<unsigned int,unsigned int>ss[100010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(unsigned int i=1;i<=n;++i)
cin>>v[i].first>>v[i].second;
sort(v+1,v+n+1);
for(unsigned 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;
}
}
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |