#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("CALC", 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);
debug(A, B, C, D);
return ((t1 - t0) * (A + D + min(B, C) + 2 * cnt - 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--;
}
debug(ans);
}
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 'int calc(int, int)':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:94:5: note: in expansion of macro 'debug'
94 | debug("CALC", t0, t1, cnt);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:103:5: note: in expansion of macro 'debug'
103 | debug(A, B, C, D);
| ^~~~~
Main.cpp: In function 'void miku()':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:128:9: note: in expansion of macro 'debug'
128 | debug(t);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:130:13: note: in expansion of macro 'debug'
130 | debug("KICK", id);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:133:13: note: in expansion of macro 'debug'
133 | debug("PUSH", id);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:137:13: note: in expansion of macro 'debug'
137 | debug("POP", id);
| ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
Main.cpp:141:9: note: in expansion of macro 'debug'
141 | debug(ans);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6940 KB |
Output is correct |
5 |
Correct |
3 ms |
6940 KB |
Output is correct |
6 |
Correct |
3 ms |
6940 KB |
Output is correct |
7 |
Correct |
3 ms |
6936 KB |
Output is correct |
8 |
Correct |
3 ms |
6940 KB |
Output is correct |
9 |
Correct |
3 ms |
6876 KB |
Output is correct |
10 |
Correct |
3 ms |
6940 KB |
Output is correct |
11 |
Correct |
3 ms |
6940 KB |
Output is correct |
12 |
Correct |
4 ms |
6940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6940 KB |
Output is correct |
5 |
Correct |
3 ms |
6940 KB |
Output is correct |
6 |
Correct |
3 ms |
6940 KB |
Output is correct |
7 |
Correct |
3 ms |
6936 KB |
Output is correct |
8 |
Correct |
3 ms |
6940 KB |
Output is correct |
9 |
Correct |
3 ms |
6876 KB |
Output is correct |
10 |
Correct |
3 ms |
6940 KB |
Output is correct |
11 |
Correct |
3 ms |
6940 KB |
Output is correct |
12 |
Correct |
4 ms |
6940 KB |
Output is correct |
13 |
Correct |
3 ms |
6940 KB |
Output is correct |
14 |
Correct |
1 ms |
6688 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6884 KB |
Output is correct |
17 |
Correct |
3 ms |
6940 KB |
Output is correct |
18 |
Correct |
3 ms |
6940 KB |
Output is correct |
19 |
Correct |
3 ms |
6940 KB |
Output is correct |
20 |
Correct |
4 ms |
6940 KB |
Output is correct |
21 |
Correct |
3 ms |
6940 KB |
Output is correct |
22 |
Correct |
3 ms |
6940 KB |
Output is correct |
23 |
Correct |
3 ms |
6936 KB |
Output is correct |
24 |
Correct |
3 ms |
6936 KB |
Output is correct |
25 |
Correct |
3 ms |
6940 KB |
Output is correct |
26 |
Correct |
3 ms |
6940 KB |
Output is correct |
27 |
Correct |
4 ms |
6940 KB |
Output is correct |
28 |
Correct |
3 ms |
6936 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6488 KB |
Output is correct |
33 |
Correct |
1 ms |
6492 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6940 KB |
Output is correct |
5 |
Correct |
3 ms |
6940 KB |
Output is correct |
6 |
Correct |
3 ms |
6940 KB |
Output is correct |
7 |
Correct |
3 ms |
6936 KB |
Output is correct |
8 |
Correct |
3 ms |
6940 KB |
Output is correct |
9 |
Correct |
3 ms |
6876 KB |
Output is correct |
10 |
Correct |
3 ms |
6940 KB |
Output is correct |
11 |
Correct |
3 ms |
6940 KB |
Output is correct |
12 |
Correct |
4 ms |
6940 KB |
Output is correct |
13 |
Correct |
3 ms |
6940 KB |
Output is correct |
14 |
Correct |
1 ms |
6688 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6884 KB |
Output is correct |
17 |
Correct |
3 ms |
6940 KB |
Output is correct |
18 |
Correct |
3 ms |
6940 KB |
Output is correct |
19 |
Correct |
3 ms |
6940 KB |
Output is correct |
20 |
Correct |
4 ms |
6940 KB |
Output is correct |
21 |
Correct |
3 ms |
6940 KB |
Output is correct |
22 |
Correct |
3 ms |
6940 KB |
Output is correct |
23 |
Correct |
3 ms |
6936 KB |
Output is correct |
24 |
Correct |
3 ms |
6936 KB |
Output is correct |
25 |
Correct |
3 ms |
6940 KB |
Output is correct |
26 |
Correct |
3 ms |
6940 KB |
Output is correct |
27 |
Correct |
4 ms |
6940 KB |
Output is correct |
28 |
Correct |
3 ms |
6936 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6488 KB |
Output is correct |
33 |
Correct |
1 ms |
6492 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Incorrect |
5 ms |
6936 KB |
Output isn't correct |
36 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6940 KB |
Output is correct |
5 |
Correct |
3 ms |
6940 KB |
Output is correct |
6 |
Correct |
3 ms |
6940 KB |
Output is correct |
7 |
Correct |
3 ms |
6936 KB |
Output is correct |
8 |
Correct |
3 ms |
6940 KB |
Output is correct |
9 |
Correct |
3 ms |
6876 KB |
Output is correct |
10 |
Correct |
3 ms |
6940 KB |
Output is correct |
11 |
Correct |
3 ms |
6940 KB |
Output is correct |
12 |
Correct |
4 ms |
6940 KB |
Output is correct |
13 |
Correct |
3 ms |
6940 KB |
Output is correct |
14 |
Correct |
1 ms |
6688 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6884 KB |
Output is correct |
17 |
Correct |
3 ms |
6940 KB |
Output is correct |
18 |
Correct |
3 ms |
6940 KB |
Output is correct |
19 |
Correct |
3 ms |
6940 KB |
Output is correct |
20 |
Correct |
4 ms |
6940 KB |
Output is correct |
21 |
Correct |
3 ms |
6940 KB |
Output is correct |
22 |
Correct |
3 ms |
6940 KB |
Output is correct |
23 |
Correct |
3 ms |
6936 KB |
Output is correct |
24 |
Correct |
3 ms |
6936 KB |
Output is correct |
25 |
Correct |
3 ms |
6940 KB |
Output is correct |
26 |
Correct |
3 ms |
6940 KB |
Output is correct |
27 |
Correct |
4 ms |
6940 KB |
Output is correct |
28 |
Correct |
3 ms |
6936 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6488 KB |
Output is correct |
33 |
Correct |
1 ms |
6492 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Incorrect |
5 ms |
6936 KB |
Output isn't correct |
36 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6940 KB |
Output is correct |
5 |
Correct |
3 ms |
6940 KB |
Output is correct |
6 |
Correct |
3 ms |
6940 KB |
Output is correct |
7 |
Correct |
3 ms |
6936 KB |
Output is correct |
8 |
Correct |
3 ms |
6940 KB |
Output is correct |
9 |
Correct |
3 ms |
6876 KB |
Output is correct |
10 |
Correct |
3 ms |
6940 KB |
Output is correct |
11 |
Correct |
3 ms |
6940 KB |
Output is correct |
12 |
Correct |
4 ms |
6940 KB |
Output is correct |
13 |
Correct |
3 ms |
6940 KB |
Output is correct |
14 |
Correct |
1 ms |
6688 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6884 KB |
Output is correct |
17 |
Correct |
3 ms |
6940 KB |
Output is correct |
18 |
Correct |
3 ms |
6940 KB |
Output is correct |
19 |
Correct |
3 ms |
6940 KB |
Output is correct |
20 |
Correct |
4 ms |
6940 KB |
Output is correct |
21 |
Correct |
3 ms |
6940 KB |
Output is correct |
22 |
Correct |
3 ms |
6940 KB |
Output is correct |
23 |
Correct |
3 ms |
6936 KB |
Output is correct |
24 |
Correct |
3 ms |
6936 KB |
Output is correct |
25 |
Correct |
3 ms |
6940 KB |
Output is correct |
26 |
Correct |
3 ms |
6940 KB |
Output is correct |
27 |
Correct |
4 ms |
6940 KB |
Output is correct |
28 |
Correct |
3 ms |
6936 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6488 KB |
Output is correct |
33 |
Correct |
1 ms |
6492 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Correct |
807 ms |
83384 KB |
Output is correct |
36 |
Correct |
825 ms |
84896 KB |
Output is correct |
37 |
Correct |
780 ms |
84144 KB |
Output is correct |
38 |
Correct |
781 ms |
82864 KB |
Output is correct |
39 |
Correct |
780 ms |
83152 KB |
Output is correct |
40 |
Correct |
1 ms |
6492 KB |
Output is correct |
41 |
Correct |
1 ms |
6488 KB |
Output is correct |
42 |
Correct |
650 ms |
82568 KB |
Output is correct |
43 |
Correct |
648 ms |
83576 KB |
Output is correct |
44 |
Correct |
658 ms |
83056 KB |
Output is correct |
45 |
Correct |
579 ms |
84392 KB |
Output is correct |
46 |
Correct |
581 ms |
83244 KB |
Output is correct |
47 |
Correct |
591 ms |
82860 KB |
Output is correct |
48 |
Correct |
635 ms |
83544 KB |
Output is correct |
49 |
Correct |
665 ms |
84288 KB |
Output is correct |
50 |
Correct |
654 ms |
83568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6940 KB |
Output is correct |
5 |
Correct |
3 ms |
6940 KB |
Output is correct |
6 |
Correct |
3 ms |
6940 KB |
Output is correct |
7 |
Correct |
3 ms |
6936 KB |
Output is correct |
8 |
Correct |
3 ms |
6940 KB |
Output is correct |
9 |
Correct |
3 ms |
6876 KB |
Output is correct |
10 |
Correct |
3 ms |
6940 KB |
Output is correct |
11 |
Correct |
3 ms |
6940 KB |
Output is correct |
12 |
Correct |
4 ms |
6940 KB |
Output is correct |
13 |
Correct |
3 ms |
6940 KB |
Output is correct |
14 |
Correct |
1 ms |
6688 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6884 KB |
Output is correct |
17 |
Correct |
3 ms |
6940 KB |
Output is correct |
18 |
Correct |
3 ms |
6940 KB |
Output is correct |
19 |
Correct |
3 ms |
6940 KB |
Output is correct |
20 |
Correct |
4 ms |
6940 KB |
Output is correct |
21 |
Correct |
3 ms |
6940 KB |
Output is correct |
22 |
Correct |
3 ms |
6940 KB |
Output is correct |
23 |
Correct |
3 ms |
6936 KB |
Output is correct |
24 |
Correct |
3 ms |
6936 KB |
Output is correct |
25 |
Correct |
3 ms |
6940 KB |
Output is correct |
26 |
Correct |
3 ms |
6940 KB |
Output is correct |
27 |
Correct |
4 ms |
6940 KB |
Output is correct |
28 |
Correct |
3 ms |
6936 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6488 KB |
Output is correct |
33 |
Correct |
1 ms |
6492 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Incorrect |
5 ms |
6936 KB |
Output isn't correct |
36 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6940 KB |
Output is correct |
5 |
Correct |
3 ms |
6940 KB |
Output is correct |
6 |
Correct |
3 ms |
6940 KB |
Output is correct |
7 |
Correct |
3 ms |
6936 KB |
Output is correct |
8 |
Correct |
3 ms |
6940 KB |
Output is correct |
9 |
Correct |
3 ms |
6876 KB |
Output is correct |
10 |
Correct |
3 ms |
6940 KB |
Output is correct |
11 |
Correct |
3 ms |
6940 KB |
Output is correct |
12 |
Correct |
4 ms |
6940 KB |
Output is correct |
13 |
Correct |
3 ms |
6940 KB |
Output is correct |
14 |
Correct |
1 ms |
6688 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
3 ms |
6884 KB |
Output is correct |
17 |
Correct |
3 ms |
6940 KB |
Output is correct |
18 |
Correct |
3 ms |
6940 KB |
Output is correct |
19 |
Correct |
3 ms |
6940 KB |
Output is correct |
20 |
Correct |
4 ms |
6940 KB |
Output is correct |
21 |
Correct |
3 ms |
6940 KB |
Output is correct |
22 |
Correct |
3 ms |
6940 KB |
Output is correct |
23 |
Correct |
3 ms |
6936 KB |
Output is correct |
24 |
Correct |
3 ms |
6936 KB |
Output is correct |
25 |
Correct |
3 ms |
6940 KB |
Output is correct |
26 |
Correct |
3 ms |
6940 KB |
Output is correct |
27 |
Correct |
4 ms |
6940 KB |
Output is correct |
28 |
Correct |
3 ms |
6936 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6488 KB |
Output is correct |
33 |
Correct |
1 ms |
6492 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Incorrect |
5 ms |
6936 KB |
Output isn't correct |
36 |
Halted |
0 ms |
0 KB |
- |