#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 3> p3i;
const int MXN = 1000005, mod = 1000003, INF = 2e9;
int n, a[MXN];
int tg[MXN], cnt;
vector<p3i> op;
ll tri(int l, int r) {
return ((l + r - 1) * (r - l) / 2) % mod;
}
pii operator+(pii a, pii b) {
return mp(min(a.fs, b.fs), max(a.sc, b.sc));
}
struct SMG1 {
pii val[MXN * 2];
void init(int _n) {
fill(val, val + 2 * n, mp(INF, -INF));
}
void modify(int p, pii v) {
val[p += n] = v;
for (p >>= 1; p; p >>= 1) val[p] = val[p << 1] + val[p << 1 | 1];
}
pii query(int l, int r) {
pii ans = mp(INF, -INF);
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = ans + val[l++];
if (r & 1) ans = ans + val[--r];
}
return ans;
}
} S;
struct SMG2 {
int val[MXN * 2];
void init(int n, int *a) {
copy(a, a + n, val + n);
for (int i = n - 1; i; i--) val[i] = min(val[i << 1], val[i << 1 | 1]);
}
void modify(int p, int v) {
val[p += n] = v;
for (p >>= 1; p; p >>= 1) val[p] = min(val[p << 1], val[p << 1 | 1]);
}
int query(int l, int r) {
int ans = INF;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = min(ans, val[l++]);
if (r & 1) ans = min(ans, val[--r]);
}
return ans;
}
} smg;
void GET_TG() {
int l = 0, r = n - 1;
int now = 0, big = *max_element(a, a + n);
while (a[l] < big) {
now = max(now, a[l]);
tg[l] = now;
l++;
}
now = 0;
while (a[r] < big) {
now = max(now, a[r]);
tg[r] = now;
r--;
}
FOR(i, l, r + 1) tg[i] = big;
}
int calc(int t0, int t1) {
if (cnt == 0) return 0;
if (t0 == t1) return 0;
// debug(t0, t1, cnt);
if (cnt == 1) {
int x = S.query(0, n).fs;
int A = smg.query(0, x), B = smg.query(x + 1, n);
return ((t1 - t0) * (A + B) + tri(t0, t1)) % mod;
}
auto [l, r] = S.query(0, n);
int A = smg.query(0, l), B = smg.query(l + 1, n);
int C = smg.query(0, r), D = smg.query(r + 1, n);
return ((t1 - t0) * (A + D + min(B, C) + 3) % mod + (3 * cnt - 3) * tri(t0, t1) % mod) % mod;
}
void miku() {
cin >> n;
FOR(i, 0, n) cin >> a[i];
GET_TG();
FOR(i, 0, n) cout << a[i] << ' ';
cout << endl;
FOR(i, 0, n) cout << tg[i] << ' ';
cout << endl;
S.init(n);
smg.init(n, a);
FOR(i, 0, n) {
op.push_back(p3i{a[i], 1, i});
op.push_back(p3i{a[i], 2, i});
op.push_back(p3i{tg[i], 3, i});
}
sort(op.begin(), op.end());
int time = 0;
ll ans = 0;
for (auto [t, tp, id] : op) {
ans = (ans + calc(time, t)) % mod;
time = t;
debug(t);
if (tp == 1) {
debug("KICK", id);
smg.modify(id, INF);
} else if (tp == 2) {
debug("PUSH", id);
S.modify(id, mp(id, id));
cnt++;
} else {
debug("POP", id);
S.modify(id, mp(INF, -INF));
cnt--;
}
}
cout << ans << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message
Main.cpp: In function 'void miku()':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:127:9: note: in expansion of macro 'debug'
127 | debug(t);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:129:13: note: in expansion of macro 'debug'
129 | debug("KICK", id);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:132:13: note: in expansion of macro 'debug'
132 | debug("PUSH", id);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:136:13: note: in expansion of macro 'debug'
136 | debug("POP", id);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |