#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
constexpr int MOD = 1e6 + 3;
int n;
ll a[1001000], b[1001000];
vector<array<int, 2>> Ev[1001000];
struct Seg{
ll tree[2002000];
int sz;
void init(int n){
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
void update(int p, ll x){
p += sz;
tree[p] = x;
for (p>>=1;p;p>>=1) tree[p] = min(tree[p<<1], tree[p<<1|1]);
}
ll query(int l, int r){
++r;
ll ret = INF;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = min(ret, tree[l++]);
if (r&1) ret = min(ret, tree[--r]);
}
return ret;
}
}tree;
void genB(){
int idx = max_element(a+1, a+n+1) - a;
int cur = 0;
for (int i=1;i<=idx;i++){
if (cur <= a[i]){
b[i] = a[i];
cur = a[i];
}
else b[i] = cur;
}
cur = 0;
for (int i=n;i>=idx;i--){
if (cur <= a[i]){
b[i] = a[i];
cur = a[i];
}
else b[i] = cur;
}
}
ll rans;
int cnt;
void dfs(vector<int> A, ll cur){
cnt++;
if (cnt > 1e5) {rans = -1; return;}
// for (auto &x:A) printf("%d ", x);
// printf("-> %lld\n", cur);
int idx = max_element(A.begin(), A.end()) - A.begin();
bool flag = 1;
for (int i=0;i<idx;i++) if (A[i] > A[i+1]) flag = 0;
for (int i=(int)A.size()-1;i>idx;i--) if (A[i] > A[i-1]) flag = 0;
if (flag){
// printf("ok cur = %lld\n", cur);
rans = min(rans, cur);
return;
}
for (int i=0;i<(int)A.size();i++){
for (int j=i+1;j<(int)A.size();j++){
for (int k=j+1;k<(int)A.size();k++){
cnt++;
if (cnt > 1e5) {rans = -1; return;}
if (A[i] > A[j] && A[j] < A[k]){
cur += A[i] + A[j] + A[k];
A[j]++;
dfs(A, cur);
A[j]--;
cur -= A[i] + A[j] + A[k];
}
// if (i==0 && j==1 && k==6) printf("ok %d %d %d\n", A[i], A[j], A[k]);
}
}
}
}
ll naive(){
cnt = 0;
vector<int> A;
for (int i=1;i<=n;i++) A.push_back(a[i]);
rans = INF;
dfs(A, 0);
return rans;
}
ll sum(ll l, ll r){
assert(l<=r);
assert(r < (int)(1e9 + 100));
return (r*(r+1) / 2 - l*(l-1) / 2) % MOD;
}
ll solve(){
a[0] = INF;
// int H = *max_element(a+1, a+n+1);
// for (int i=1;i<=H;i++) Ev[i].clear();
// scanf("%d", &n);
// for (int i=1;i<=n;i++) scanf("%lld", a+i);
// printf("%lld\n", naive());
genB();
vector<int> C;
for (int i=1;i<=n;i++){
C.push_back(a[i]);
C.push_back(b[i]);
}
C.push_back(0);
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
for (int i=1;i<=n;i++){
a[i] = lower_bound(C.begin(), C.end(), a[i]) - C.begin();
b[i] = lower_bound(C.begin(), C.end(), b[i]) - C.begin();
Ev[a[i]].push_back({0, i});
Ev[b[i]].push_back({1, i});
// assert(a[i] <= b[i]);
// assert(b[i] <= H);
}
multiset<int> st;
tree.init(n+1);
ll ans = 0;
for (int i=1;i<(int)C.size();i++){
sort(Ev[i].begin(), Ev[i].end());
for (auto &[typ, pos]:Ev[i]){
if (typ==0){
tree.update(pos, INF);
st.insert(pos);
}
else{
st.erase(st.find(pos));
}
}
int cnt = st.size();
if (cnt==0) continue;
int s = *st.begin(), e = *st.rbegin();
ll p0 = tree.query(1, s-1), pk = tree.query(e+1, n), p = tree.query(1, n);
// printf("\n%d -> %d:\n", i, i+1);
// for (auto &x:st) printf("%d ", x);
// printf("\n");
// printf(" ok %lld %lld %lld\n", p0, pk, p);
assert(p0 < INF && pk < INF && p < INF);
assert(p0 > i && pk > i && p > i);
if (cnt >= 2){
ans += (p0 + pk + p) * (C[i+1] - C[i]);
ans %= MOD;
ans += sum(C[i]+1, C[i+1]) * (cnt*2 - 3);
ans %= MOD;
ans += sum(C[i], C[i+1]-1) * cnt;
ans %= MOD;
}
else{
ans += (p0 + pk) * (C[i+1] - C[i]);
ans %= MOD;
ans += sum(C[i], C[i+1]-1) * cnt;
ans %= MOD;
}
// if (cnt >= 2) ans += p0 + pk + p + (ll)(i+1) * (cnt*2 - 3) + (ll)i*cnt;
// else ans += p0 + pk + i;
// ans %= MOD;
}
return ans;
}
mt19937 seed(69);
uniform_int_distribution<int> rng(0, 2147483647);
int getrand(int l, int r){return rng(seed) % (r-l+1) + l;}
void gen(){
n = getrand(1, 7);
for (int i=1;i<=n;i++) a[i] = getrand(1, 10);
}
void stress(int tc){
// printf("--------------------------------------\n");
// printf("Stress #%d\n", tc);
gen();
// printf("Input:\n");
// printf("%d\n", n);
// for (int i=1;i<=n;i++) printf("%lld ", a[i]);
// printf("\n");
ll ans = naive();
ll out = solve();
// printf("Answer: %lld\n", ans);
// printf("Output: %lld\n", out);
if (ans!=out && ans!=-1){
printf("--------------------------------------\n");
printf("Stress #%d\n", tc);
printf("Input:\n");
printf("%d\n", n);
for (int i=1;i<=n;i++) printf("%lld ", a[i]);
printf("\n");
printf("Answer: %lld\n", ans);
printf("Output: %lld\n", out);
}
if (tc%10000==0) printf("ok %d done\n", tc);
assert(ans==out || ans==-1);
}
signed main(){
// for (int i=1;;i++) stress(i);
scanf("%lld", &n);
for (int i=1;i<=n;i++) scanf("%lld", a+i);
printf("%lld\n", solve());
}
Compilation message
Main.cpp: In function 'void stress(long long int)':
Main.cpp:245:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
245 | printf("Stress #%d\n", tc);
| ~^ ~~
| | |
| int long long int
| %lld
Main.cpp:248:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
248 | printf("%d\n", n);
| ~^ ~
| | |
| int long long int
| %lld
Main.cpp:256:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
256 | if (tc%10000==0) printf("ok %d done\n", tc);
| ~^ ~~
| | |
| int long long int
| %lld
Main.cpp: In function 'int main()':
Main.cpp:264:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
264 | scanf("%lld", &n);
| ~~~~~^~~~~~~~~~~~
Main.cpp:265:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
265 | for (int i=1;i<=n;i++) scanf("%lld", a+i);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
