//subtask2
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;
struct stree {
#define lc v*2
#define rc v*2+1
vector <int> tree;
stree (int s) {
tree.resize(s * 4);
}
void pushup(int v) {
tree[v] = max(tree[lc], tree[rc]);
}
void update(int v, int tl, int tr, int p, int val) {
if (tl > p || tr < p)
return;
if (tl == tr) {
tree[v] = val;
return;
}
int tm = (tl + tr) / 2;
update(lc, tl, tm, p, val);
update(rc, tm+1, tr, p, val);
pushup(v);
}
int query(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
if (tl >= l && tr <= r)
return tree[v];
int tm = (tl + tr) / 2;
int a = query(lc, tl, tm, l, r);
int b = query(rc, tm+1, tr, l, r);
return max(a, b);
}
};
int main() {
int n;
cin >> n;
multiset <pair <int, int>> s;
multiset <pair <int, int>> rngs;
rngs.insert({1, n});
stree tree(n+1);
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
tree.update(1, 1, n, i, t);
s.insert({t, i});
}
vector <bool> rem(n+1);
ll ans = 0;
while (!s.empty()) {
int mx = s.rbegin()->first;
int pos = s.rbegin()->second;
auto tp = rngs.upper_bound({pos+1, pos});
tp--;
int l = tp->first, r = tp->second;
rngs.erase(tp);
s.erase(--s.end());
int added = 0;
if (pos+1 <= n && !rem[pos+1]) {
ans += tree.query(1, 1, n, pos+1, r);
added++;
}
if (pos-1 >= 1 && !rem[pos-1]) {
ans += tree.query(1, 1, n, l, pos-1);
added++;
}
rem[pos] = true;
tree.update(1, 1, n, pos, 0);
ans += mx * added;
if (l == r)
continue;
if (pos == l)
rngs.insert({l+1, r});
else if (pos == r)
rngs.insert({l, r-1});
else {
rngs.insert({l, pos-1});
rngs.insert({pos+1, r});
}
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
105 ms |
5712 KB |
Output is correct |
2 |
Correct |
72 ms |
4948 KB |
Output is correct |
3 |
Correct |
69 ms |
4692 KB |
Output is correct |
4 |
Correct |
79 ms |
5456 KB |
Output is correct |
5 |
Correct |
121 ms |
7764 KB |
Output is correct |
6 |
Correct |
81 ms |
7596 KB |
Output is correct |
7 |
Correct |
69 ms |
6748 KB |
Output is correct |
8 |
Correct |
63 ms |
6180 KB |
Output is correct |
9 |
Correct |
42 ms |
4176 KB |
Output is correct |
10 |
Correct |
81 ms |
7760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |