Submission #439016

#	Time	Username	Problem	Language	Result	Execution time	Memory
439016		Hausdorf	Mountains (NOI20_mountains)	C++17	100 / 100	897 ms	27460 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define itn int
#define fi first
#define se second
#pragma optimizatiob ("O3")
#pragma GCC target ("avx2")
#pragma optimization ("unroll_loops")

struct segtree {
    vector<int> tree;
    vector<int> promise;
    segtree (int n) {
        tree.resize(4 * n, 0);
        promise.resize(4 * n, 0);
    }
    void push (int id, int l, int r) {
        tree[id] += (r - l) * promise[id];
        if (r - l > 1) {
            promise[2 * id + 1] += promise[id];
            promise[2 * id + 2] += promise[id];
        }
        promise[id] = 0;
    }
    void upd (int id, int l, int r, int lq, int rq, int up) {
        push(id, l, r);
        if (l >= lq && r <= rq) {
            promise[id] += up;
            push(id, l, r);
            return;
        }
        if (l >= rq || r <= lq) {
            return;
        }
        int m = (r + l) / 2;
        upd(2 * id + 1, l, m, lq, rq, up);
        upd(2 * id + 2, m, r, lq, rq, up);
        tree[id] = tree[id * 2 + 1] + tree[id * 2 + 2];
    }
    int get (int id, int l, int r, int q) {
        push(id, l, r);
        if (r - l == 1 && l == q) {
            return tree[id];
        }
        if (q >= r || q < l)
            return 0;
        int m = (r + l) / 2;
        return get(id * 2 + 1, l, m, q) + get(id * 2 + 2, m, r, q);
    }
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<pair<ll, int>> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i].fi;
        h[i].se = i;
    }
    sort(h.begin(), h.end());
    vector<int> lessleft(n, 0), lessright(n, 0), been(n, 0);
    segtree templeft(n), tempright(n);
    for (int i = 1;  i < n; ++i) {
        if (h[i].fi == h[i - 1].fi) {
            been[i] = 1 + been[i - 1];
        }
    }
    //for (int i = n - 2; i > -1; --i) {
    //    if (a[i] == a[i + 1])
    //        been[i] = been[i + 1];
    //}
    for (int i = 0; i < n; ++i) {
        int ind = h[i].se;
        lessleft[ind] = templeft.get(0, 0, n, ind) - been[i];
        lessright[ind] = tempright.get(0, 0, n, ind);
        //cout << lessleft[ind] << ' ' << lessright[ind] << '\n';
        if (ind == 0) {
            templeft.upd(0, 0, n, ind + 1, n, 1);
        }
        else if (ind == n - 1) {
            tempright.upd(0, 0, n, 0, ind, 1);
        }
        else {
            templeft.upd(0, 0, n, ind + 1, n, 1);
            tempright.upd(0, 0, n, 0, ind, 1);
        }
    }
    /*lessleft[0] = lessright[n - 1] = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (h[j] < h[i])
                ++lessleft[i];
        }
    }
    for (int i = n - 2; i >= 0; --i) {
        for (int j = n - 1; j > i; --j) {
            if (h[j] < h[i])
                ++lessright[i];
        }
    }*/
    ll ans = 0;
    for (int i = 0; i < n; ++i)
        ans += 1ll * lessleft[i] * lessright[i];
    cout << ans;
}

Compilation message (stderr)

Mountains.cpp:8: warning: ignoring '#pragma optimizatiob ' [-Wunknown-pragmas]
    8 | #pragma optimizatiob ("O3")
      | 
Mountains.cpp:10: warning: ignoring '#pragma optimization ' [-Wunknown-pragmas]
   10 | #pragma optimization ("unroll_loops")
      |

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12