| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1303986 | activedeltorre | Real Mountains (CCO23_day1problem2) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
long long mod=1000003;
map<long long,vector<long long> >event;
long long v[1000005];
long long along long[2500005];
long long inf=1e9,n;
long long pzst=1,pzdr;
void update(long long node,long long st,long long dr,long long poz,long long val)
{
if(st>poz || dr<poz)
{
return;
}
if(st==dr)
{
along long[node]=val;
return;
}
long long mij=(st+dr)/2;
update(node*2,st,mij,poz,val);
update(node*2+1,mij+1,dr,poz,val);
along long[node]=min(along long[node*2],along long[node*2+1]);
}
long long query(long long node,long long st,long long dr,long long qst,long long qdr)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
{
return inf;
}
if(qst<=st && dr<=qdr)
{
return along long[node];
}
long long mij=(st+dr)/2;
return min(query(node*2,st,mij,qst,qdr),query(node*2+1,mij+1,dr,qst,qdr));
}
set<long long>s0;
void update(long long poz)
{
s0.insert(poz);
update(1,1,n,poz,inf);
}
long long gaus(long long a)
{
return (a*(a+1)/2)%mod;
}
long long recalc(long long val,long long iter)
{
while(s0.size() && *s0.begin()==pzst)
{
s0.erase(s0.begin());
pzst++;
}
while(s0.size() && *prev(s0.end())==pzdr)
{
s0.erase(prev(s0.end()));
pzdr--;
}
if(s0.size()==0)
{
return 0;
}
long long minimpref=query(1,1,n,1,*s0.begin());
long long minimsuf=query(1,1,n,*prev(s0.end()),n);
long long minimtot=query(1,1,n,1,n);
if(s0.size()==1)
{
return ((minimpref+minimsuf)*iter+gaus(val+iter-1)-gaus(val-1))%mod;
}
return ((minimpref+minimsuf+minimtot)*iter+s0.size()*(gaus(val+iter-1)-gaus(val-1))+(s0.size()*2-3)*(gaus(val+iter)-gaus(val)))%mod;
}
signed main()
{
long long i,j,k,l,t,h,w,x,m,a,b;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
pzdr=n;
for(long long i=1;i<=n;i++)
{
cin>>v[i];
event[v[i]].push_back(i);
update(1,1,n,i,v[i]);
}
long long tot=0;
for(auto it=event.begin();it!=event.end();it++)
{
for(auto k:it->second)
{
update(k);
}
auto it2=it;
it2++;
if(it2!=event.end())
{
tot=(tot+recalc(it->first,(it2->first-it->first)))%mod;
}
}
cout<<tot%mod;
return 0;
}