#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using llf = long double;
const int mod = 1e6 + 3; // 1e9 + 7;//993244853;
// I don't remember the credit of modint, but it's not mine.
// I don't remember the credit of FFT, but it's probably mine.
// Polynomial library is due to adamant:
// https://github.com/cp-algorithms/cp-algorithms-aux/blob/master/src/polynomial.cpp
// To use polynomial sqrt, need to amend sqrt for modint.
struct mint {
int val;
mint() { val = 0; }
mint(const lint &v) {
val = (-mod <= v && v < mod) ? v : v % mod;
if (val < 0)
val += mod;
}
friend ostream &operator<<(ostream &os, const mint &a) { return os << a.val; }
friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; }
friend bool operator!=(const mint &a, const mint &b) { return !(a == b); }
friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; }
mint operator-() const { return mint(-val); }
mint &operator+=(const mint &m) {
if ((val += m.val) >= mod)
val -= mod;
return *this;
}
mint &operator-=(const mint &m) {
if ((val -= m.val) < 0)
val += mod;
return *this;
}
mint &operator*=(const mint &m) {
val = (lint)val * m.val % mod;
return *this;
}
friend mint ipow(mint a, lint p) {
mint ans = 1;
for (; p; p /= 2, a *= a)
if (p & 1)
ans *= a;
return ans;
}
mint inv() const { return ipow(*this, mod - 2); }
mint &operator/=(const mint &m) { return (*this) *= m.inv(); }
friend mint operator+(mint a, const mint &b) { return a += b; }
friend mint operator-(mint a, const mint &b) { return a -= b; }
friend mint operator*(mint a, const mint &b) { return a *= b; }
friend mint operator/(mint a, const mint &b) { return a /= b; }
operator int64_t() const { return val; }
};
mint bino(int n, int k) {
mint up = 1, dn = 1;
for (int i = 0; i < k; i++) {
up *= mint(n - i);
dn *= mint(i + 1);
}
return up / dn;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
lint tot = 0;
for (int i = 1; i < 100; i++) {
int l = 0, r = n;
while (l < n && a[l] <= i)
l++;
while (r > l && a[r - 1] <= i)
r--;
vector<int> pos;
vector<pi> mswp;
int mx = 1e9;
for (int j = l; j < r; j++) {
if (a[j] <= i) {
pos.push_back(j);
mswp.push_back({mx, 0});
} else
mx = min(mx, a[j]);
}
if (sz(pos) == 0)
continue;
int ptr = sz(pos);
mx = 1e9;
for (int j = r - 1; j >= l; j--) {
if (a[j] <= i) {
pos.push_back(j);
mswp[--ptr][1] = mx;
} else
mx = min(mx, a[j]);
}
vector<int> lsave(sz(pos)), rsave(sz(pos));
for (int j = 0; j < sz(pos); j++) {
tot += mswp[j][0] + mswp[j][1] + i;
lsave[j] = mswp[j][1] - i;
rsave[j] = mswp[j][0] - i;
}
lint run = accumulate(all(rsave), 0ll);
lint save = 0;
for (int j = 0; j < sz(pos); j++) {
run -= rsave[j];
save = max(save, run);
run += lsave[j];
}
tot -= save;
}
cout << tot % 1000003 << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
