#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const ll p=1e6+3;
const ll maxn=1e9;
struct node{
ll val=0,tag1=maxn,tag2=0;
}tri[4000010];
void init(ll l,ll r,int id){
tri[id].val=0,tri[id].tag1=maxn,tri[id].tag2=0;
if(l==r)return;
ll m=(l+r)>>1;
init(l,m,id*2+1);
init(m+1,r,id*2+2);
return;
}
void push(ll l,ll r,int id){
//cout<<l<<" "<<r<<" "<<id<<" ";
if(tri[id].tag2!=0){
//cout<<"2\n";
tri[id].val=((r-l+1)*(r+l)/2)%p;
}else if(tri[id].tag1<maxn){
//cout<<"1\n";
tri[id].val=((r-l+1)*tri[id].tag1)%p;
}
if(l!=r){
tri[id*2+1].tag1=min(tri[id].tag1,tri[id*2+1].tag1);
tri[id*2+2].tag1=min(tri[id].tag1,tri[id*2+2].tag1);
tri[id*2+1].tag2|=tri[id].tag2;
tri[id*2+2].tag2|=tri[id].tag2;
}
}
void pull(ll l,ll r,int id){
tri[id].val=(tri[id*2+1].val+tri[id*2+2].val)%p;
return;
}
void modify1(int l,int r,int L,int R,int id,ll x){
push(l,r,id);
if(l==L&&r==R){
tri[id].tag1=min(tri[id].tag1,x);
push(l,r,id);
return;
}
int m=(l+r)>>1;
if(R<=m)modify1(l,m,L,R,id*2+1,x);
else if(m<L)modify1(m+1,r,L,R,id*2+2,x);
else {
modify1(l,m,L,m,id*2+1,x);
modify1(m+1,r,m+1,R,id*2+2,x);
}
pull(l,r,id);
return;
}
void modify2(int l,int r,int L,int R,int id){
push(l,r,id);
if(l==L&&r==R){
tri[id].tag2=1;
push(l,r,id);
return;
}
int m=(l+r)>>1;
if(R<=m)modify2(l,m,L,R,id*2+1);
else if(m<L)modify2(m+1,r,L,R,id*2+2);
else {
modify2(l,m,L,m,id*2+1);
modify2(m+1,r,m+1,R,id*2+2);
}
pull(l,r,id);
return ;
}
ll query(int l, int r, int L,int R,int id){
push(l,r,id);
if(l==L&&r==R){
return tri[id].val;
}
int m=(l+r)>>1;
if(R<=m)return query(l,m,L,R,id*2+1);
else if(m<L)return query(m+1,r,L,R,id*2+2);
else {
return (query(l,m,L,m,id*2+1)+query(m+1,r,m+1,R,id*2+2))%p;
}
}
ll ans;
int n,h[1000010],mh;
vector<pair<int,int>> seg,bseg;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>h[i],mh=max(mh,h[i]);
ll pos=1,mx=0;
while(h[pos]!=mh){
if(h[pos]>mx){
mx=h[pos];
}
seg.push_back({h[pos],mx});
ans+=(mx-h[pos])*(mx+h[pos]-1)/2;
ans%=p;
pos++;
}
ll bpos=n,bmx=0;
while(h[bpos]!=mh){
if(h[bpos]>bmx){
bmx=h[bpos];
}
bseg.push_back({h[bpos],bmx});
ans+=(bmx-h[bpos])*(bmx+h[bpos]-1)/2;
ans%=p;
bpos--;
}
for(int i=pos;i<=bpos;i++){
seg.push_back({h[i],mh});
ans+=(mh-h[i])*(mh+h[i]-1)/2;
ans%=p;
}
reverse(bseg.begin(),bseg.end());
for(int i=0;i<bseg.size();i++)seg.push_back(bseg[i]);
init(1,1000000,0);
for(int i=0;i<n;i++){
// cout<<seg[i].F<<" "<<seg[i].S<<"\n";
if(seg[i].F!=seg[i].S){
//cout<<query(1,1000000,seg[i].F+1,seg[i].S,0)<<"F\n";
ans+=query(1,1000000,seg[i].F+1,seg[i].S,0);
//ans%=p;
}
modify2(1,1000000,seg[i].F,seg[i].S,0);
modify1(1,1000000,1,seg[i].F,0,seg[i].F);
}
reverse(seg.begin(),seg.end());
init(1,1000000,0);
for(int i=0;i<n;i++){
//cout<<seg[i].F<<" "<<seg[i].S<<" "<<query(1,1000000,3,3,0)<<"\n";
if(seg[i].F!=seg[i].S){
// cout<<query(1,1000000,seg[i].F+1,seg[i].S,0)<<"B\n";
ans+=query(1,1000000,seg[i].F+1,seg[i].S,0);
//ans%=p;
}
modify2(1,1000000,seg[i].F,seg[i].S,0);
modify1(1,1000000,1,seg[i].F,0,seg[i].F);
}
cout<<ans<<"\n";
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i=0;i<bseg.size();i++)seg.push_back(bseg[i]);
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
49496 KB |
Output is correct |
2 |
Correct |
31 ms |
49488 KB |
Output is correct |
3 |
Incorrect |
33 ms |
49496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
49496 KB |
Output is correct |
2 |
Correct |
31 ms |
49488 KB |
Output is correct |
3 |
Incorrect |
33 ms |
49496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
49496 KB |
Output is correct |
2 |
Correct |
31 ms |
49488 KB |
Output is correct |
3 |
Incorrect |
33 ms |
49496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
49496 KB |
Output is correct |
2 |
Correct |
31 ms |
49488 KB |
Output is correct |
3 |
Incorrect |
33 ms |
49496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
49496 KB |
Output is correct |
2 |
Correct |
31 ms |
49488 KB |
Output is correct |
3 |
Incorrect |
33 ms |
49496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
49496 KB |
Output is correct |
2 |
Correct |
31 ms |
49488 KB |
Output is correct |
3 |
Incorrect |
33 ms |
49496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
49496 KB |
Output is correct |
2 |
Correct |
31 ms |
49488 KB |
Output is correct |
3 |
Incorrect |
33 ms |
49496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |