#include<bits/stdc++.h>
#define fori(i,a,b) for(int i = a;i <= b; i++)
#define int long long
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 5e3 + 10;
const int mod = 1e6 + 3;
int n,h[N];
int target[N];
vector<int> Q[N];
vector<int> rrh;
int calc(int l,int r)
{
return ((l + r) * (r - l + 1)/2) % mod;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r"))
{
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n;
for(int i = 1;i <= n; i++) cin >> h[i];
int suf = 0,pre = 0;
for(int i = 1;i <= n; i++) {
pre = max(pre, h[i]);
target[i] = pre ;
}
for(int i = n; i != 0; i--) {
suf = max(suf, h[i]);
target[i] = min(target[i], suf);
}
for(int i = 1;i <= n; i++) rrh.pb(h[i]);
sort(rrh.begin(),rrh.end());
rrh.resize(unique (rrh.begin(), rrh.end()) - rrh.begin());
for(int i = 1;i <= n; i++) {
h[i] = lower_bound(rrh.begin(),rrh.end(),h[i]) - rrh.begin() ;
target[i] = lower_bound(rrh.begin(),rrh.end(),target[i]) - rrh.begin() ;
//cout << h[i] << " " << target[i] << "\n";
}
for(int i = 1;i <= n; i++) {
if(h[i] != target[i]) {
Q[h[i]].pb(i);
}
}
int kq = 0;
int m = rrh.size();
for(int high = 0;high <= m - 2; high++) {
if(Q[high].size() == 0) continue;
if(Q[high].size() == 1) {
int x = 1e9 , y = 1e9 , cur = Q[high][0];
for(int j = 1; j < cur; j++) {
if(h[j] > h[cur]) x = min(x,rrh[h[j]]);
}
for(int j = cur + 1; j <= n ;j++) {
if(h[j] > h[cur]) y = min(y,rrh[h[j]]);
}
kq = (kq + (rrh[high + 1] - rrh[high])*(x + y) % mod + calc(rrh[high],rrh[high + 1] - 1) ) % mod;
h[cur]++;
if(h[cur] != target[cur]) Q[h[cur]].pb(cur);
}
else {
sort(Q[high].begin(),Q[high].end());
int pre_l = 1e9 , pre_r = 1e9 , suf_l = 1e9 , suf_r = 1e9;
int l = Q[high][0], r = Q[high].back();
for(int j = 1;j < l ; j++) {
if(h[j] > h[l]) pre_l = min(pre_l,rrh[h[j]]);
}
for(int j = l + 1;j <= n; j++) {
if(h[j] > h[l]) suf_l = min(suf_l,rrh[h[j]]);
}
for(int j = 1; j < r; j++) {
if(h[j] > h[r]) pre_r = min(pre_r,rrh[h[j]]);
}
for(int j = r + 1;j <= n; j++) {
if(h[j] > h[r]) suf_r = min(suf_r,rrh[h[j]]);
}
// kq += min(pre_l + suf_l + h[l] + h[r] + h[l] + 1 + suf_r,
// pre_r + suf_r + h[r] + h[l] + h[r] + 1 + pre_l);
// kq %= mod;
int x = ((rrh[high + 1] - rrh[high])*(pre_l + suf_l) % mod + calc(rrh[high],rrh[high + 1] - 1) +
calc(rrh[high],rrh[high + 1] - 1) % mod + calc(rrh[high] + 1,rrh[high + 1]) % mod +
(rrh[high + 1] - rrh[high]) * suf_r % mod) % mod;
int y = ((rrh[high + 1] - rrh[high])*(pre_r + suf_r) % mod + calc(rrh[high],rrh[high + 1] - 1) +
calc(rrh[high],rrh[high + 1] - 1) % mod + calc(rrh[high] + 1,rrh[high + 1]) % mod +
(rrh[high + 1] - rrh[high]) * pre_l % mod) % mod;
kq = (kq + min(x,y)) % mod;
int sz = Q[high].size();
kq += ((sz - 2) * (rrh[high + 1] - rrh[high]) % mod + 2 * calc(rrh[high],rrh[high+1]-1) % mod) % mod;
for(int idx : Q[high]) {
h[idx]++;
if(h[idx] != target[idx]) Q[h[idx]].pb(idx);
}
}
}
cout << kq % mod;
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | freopen("1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
