#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define int ll
#define _all(T) T.begin(),T.end()
const ll mod = 1e6+3;
const int inf = 1e9;
const int mxn = 1e6+10;
int arr[mxn],pref[mxn],suf[mxn],tar[mxn];
int N;
vector<int> all;
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
int seg[mxn*4];
SEG(){
fill(seg,seg+mxn*4,inf);
return;
}
void modify(int now,int l,int r,int p,int v){
if(l == r){
seg[now] = v;
return;
}
if(mid>=p)modify(ls,l,mid,p,v);
else modify(rs,mid+1,r,p,v);
seg[now] = min(seg[ls],seg[rs]);
return;
}
int getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return min(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
#undef ls
#undef rs
#undef mid
};
int lp[mxn],rp[mxn];
pii ls[mxn],rs[mxn];
int cnt[mxn];
namespace INIT{
priority_queue<int,vector<int>,greater<int>> mn;
priority_queue<int,vector<int>,less<int>> mx;
bitset<mxn> active;
vector<int> op[mxn];
void GO(){
int num = 0;
for(int i = 1;i<=N;i++){
if(arr[i] == tar[i])continue;
op[arr[i]].push_back(i);
op[tar[i]].push_back(-i);
}
for(int i = 0;i<all.size();i++){
for(auto &j:op[i]){
if(j>0){
num++;
active[j] = true;
mx.push(j);
mn.push(j);
}
else{
num--;
active[-j] = false;
}
}
cnt[i] = num;
if(!num)continue;
while(!active[mx.top()])mx.pop();
while(!active[mn.top()])mn.pop();
lp[i] = mn.top();
rp[i] = mx.top();
}
for(int i = 0;i<all.size();i++){
cerr<<i<<" "<<all[i]<<":"<<lp[i]<<' '<<rp[i]<<endl;
}
return;
}
}
namespace SWEEP{
SEG seg;
vector<int> op[mxn];
void GO(){
for(int i = 1;i<=N;i++){
op[arr[i]].push_back(i);
}
for(int i = all.size()-1;i>=0;i--){
if(cnt[i]){
ls[i].fs = seg.getval(0,0,all.size(),0,lp[i]);
ls[i].sc = seg.getval(0,0,all.size(),lp[i],all.size());
rs[i].fs = seg.getval(0,0,all.size(),0,rp[i]);
rs[i].sc = seg.getval(0,0,all.size(),rp[i],all.size());
}
for(auto &j:op[i])seg.modify(0,0,all.size(),j,i);
}
for(int i = 0;i<all.size();i++){
if(cnt[i]){
cerr<<i<<' '<<all[i]<<":"<<ls[i].fs<<' '<<ls[i].sc<<','<<rs[i].fs<<' '<<rs[i].sc<<endl;
}
}
return;
}
}
namespace GETANS{
ll ans = 0;
void GO(){
for(int i = 0;i+1<all.size();i++){
ls[i].fs = all[ls[i].fs],rs[i].fs = all[rs[i].fs];
ls[i].sc = all[ls[i].sc],rs[i].sc = all[rs[i].sc];
if(!cnt[i])continue;
if(cnt[i] == 1){
ans += (ls[i].fs+ls[i].sc)*(all[i+1]-all[i])+(all[i]+all[i+1]-1)*(all[i+1]-all[i])/2%mod;
ans %= mod;
continue;
}
if(ls[i].fs+ls[i].sc+rs[i].sc<=rs[i].fs+rs[i].sc+ls[i].fs){
ans += (ls[i].fs+ls[i].sc)*(all[i+1]-all[i])%mod;
ans += rs[i].sc*(all[i+1]-all[i])%mod+(all[i+1]+all[i]+1)*(all[i+1]-all[i])/2%mod;
}
else{
ans += (rs[i].fs+rs[i].sc)*(all[i+1]-all[i])%mod;
ans += ls[i].fs*(all[i+1]-all[i])%mod+(all[i+1]+all[i]+1)*(all[i+1]-all[i])/2%mod;
}
ans %= mod;
ans += 1ll*(cnt[i]-2)*((all[i+1]+all[i]+1)*(all[i+1]-all[i])/2%mod*2)%mod;
ans += 1ll*(cnt[i])*((all[i+1]-1+all[i])*(all[i+1]-all[i])/2%mod)%mod;
ans %= mod;
}
cout<<ans%mod<<'\n';
return;
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
arr[0] = arr[N+1] = 1e9;
for(int i = 1;i<=N;i++)cin>>arr[i],all.push_back(arr[i]);
all.push_back(0);
all.push_back(arr[0]);
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
int mx = 0;
for(int i = 1;i<=N;i++){
mx = max(arr[i],mx);
tar[i] = mx;
}
mx = 0;
for(int i = N;i>=1;i--){
mx = max(arr[i],mx);
tar[i] = min(tar[i],mx);
}
for(int i = 1;i<=N;i++){
arr[i] = lower_bound(_all(all),arr[i])-all.begin();
tar[i] = lower_bound(_all(all),tar[i])-all.begin();
}
for(int i = 1;i<=N;i++)cerr<<arr[i]<<' ';cerr<<endl;
for(int i = 1;i<=N;i++)cerr<<tar[i]<<' ';cerr<<endl;
INIT::GO();
cerr<<"INIT done"<<endl;
SWEEP::GO();
cerr<<"SWEEP done"<<endl;
GETANS::GO();
cerr<<"ANSWERED"<<endl;
}
Compilation message
Main.cpp: In function 'void INIT::GO()':
Main.cpp:68:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0;i<all.size();i++){
| ~^~~~~~~~~~~
Main.cpp:88:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0;i<all.size();i++){
| ~^~~~~~~~~~~
Main.cpp: In function 'void SWEEP::GO()':
Main.cpp:111:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 0;i<all.size();i++){
| ~^~~~~~~~~~~
Main.cpp: In function 'void GETANS::GO()':
Main.cpp:123:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i = 0;i+1<all.size();i++){
| ~~~^~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:150:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
150 | main(){
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:173:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
173 | for(int i = 1;i<=N;i++)cerr<<arr[i]<<' ';cerr<<endl;
| ^~~
Main.cpp:173:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
173 | for(int i = 1;i<=N;i++)cerr<<arr[i]<<' ';cerr<<endl;
| ^~~~
Main.cpp:174:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
174 | for(int i = 1;i<=N;i++)cerr<<tar[i]<<' ';cerr<<endl;
| ^~~
Main.cpp:174:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
174 | for(int i = 1;i<=N;i++)cerr<<tar[i]<<' ';cerr<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
84568 KB |
Output is correct |
| 2 |
Correct |
17 ms |
92764 KB |
Output is correct |
| 3 |
Correct |
18 ms |
92872 KB |
Output is correct |
| 4 |
Execution timed out |
5089 ms |
93172 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
84568 KB |
Output is correct |
| 2 |
Correct |
17 ms |
92764 KB |
Output is correct |
| 3 |
Correct |
18 ms |
92872 KB |
Output is correct |
| 4 |
Execution timed out |
5089 ms |
93172 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
84568 KB |
Output is correct |
| 2 |
Correct |
17 ms |
92764 KB |
Output is correct |
| 3 |
Correct |
18 ms |
92872 KB |
Output is correct |
| 4 |
Execution timed out |
5089 ms |
93172 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
84568 KB |
Output is correct |
| 2 |
Correct |
17 ms |
92764 KB |
Output is correct |
| 3 |
Correct |
18 ms |
92872 KB |
Output is correct |
| 4 |
Execution timed out |
5089 ms |
93172 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
84568 KB |
Output is correct |
| 2 |
Correct |
17 ms |
92764 KB |
Output is correct |
| 3 |
Correct |
18 ms |
92872 KB |
Output is correct |
| 4 |
Execution timed out |
5089 ms |
93172 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
84568 KB |
Output is correct |
| 2 |
Correct |
17 ms |
92764 KB |
Output is correct |
| 3 |
Correct |
18 ms |
92872 KB |
Output is correct |
| 4 |
Execution timed out |
5089 ms |
93172 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
84568 KB |
Output is correct |
| 2 |
Correct |
17 ms |
92764 KB |
Output is correct |
| 3 |
Correct |
18 ms |
92872 KB |
Output is correct |
| 4 |
Execution timed out |
5089 ms |
93172 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
