Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int n;
- const int maxN = (int)1e7 + 10;
- int nxt[maxN], prv[maxN];
- int fenw[maxN];
- void upd(int v, int d) {
- while (v <= n + 1) {
- fenw[v] += d;
- v = (v | (v - 1)) + 1;
- }
- }
- int get(int v) {
- int ans = 0;
- while (v > 0) {
- ans += fenw[v];
- v &= (v - 1);
- }
- return ans;
- }
- int upperBound(int sum) {
- int cur = 1;
- for (int i = 24; i >= 0; i--) {
- int ncur = cur + (1 << i) - 1;
- if (ncur <= n + 1 && fenw[ncur] <= sum) {
- sum -= fenw[ncur];
- cur = ncur + 1;
- }
- }
- return cur;
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- ios_base::sync_with_stdio(false);
- //cin >> n;
- n = (int)1e7;
- vector < pair < int, int > > all;
- for (int i = 1; i <= n; i++) {
- //cin >> a[i];
- int x = i % 237 + 23 * i % 8;
- cin >> x;
- all.emplace_back(x, i);
- }
- sort(all.begin(), all.end());
- reverse(all.begin(), all.end());
- set < int > s;
- s.insert(0);
- s.insert(n + 1);
- ll ans = 0;
- nxt[0] = n + 1;
- prv[n + 1] = 0;
- nxt[n + 1] = n + 1;
- prv[0] = 0;
- upd(n + 1, 1);
- for (auto it : all) {
- int ind = it.second;
- int pos3 = upperBound(get(ind));
- int pos4 = nxt[pos3];
- int pos2 = prv[pos3];
- int pos1 = prv[pos2];
- nxt[pos2] = ind;
- prv[ind] = pos2;
- prv[pos3] = ind;
- nxt[ind] = pos3;
- upd(ind, 1);
- if (pos2 == 0 && pos3 == n + 1) continue;
- ans += 1LL * it.first * (pos4 - pos3) * (ind - pos2) + (pos2 - pos1) * (pos3 - ind);
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement