Submission #1220430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220430		toast12	Mountains (NOI20_mountains)	C++20	100 / 100	284 ms	23920 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define lc 2*v
#define rc 2*v+1
#define tm (tl+tr)/2

struct segtree {
    vector<int> tree;
    segtree(int sz) {
        tree.resize(4*sz);
    }
    void update(int v, int tl, int tr, int pos, int val) {
        if (tr < pos || tl > pos) return;
        if (tl == tr) {
            tree[v] += val;
            return;
        }
        update(lc, tl, tm, pos, val);
        update(rc, tm+1, tr, pos, val);
        tree[v] = tree[lc]+tree[rc];
    }
    int query(int v, int tl, int tr, int r) {
        if (tl > r) return 0;
        if (tr <= r) return tree[v];
        return query(lc, tl, tm, r)+query(rc, tm+1, tr, r);
    }
};  

int main() {
    int n;
    cin >> n;
    vector<pair<ll, int>> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i].first;
        h[i].second = i;
    }
    sort(h.begin(), h.end());
    int cur = 1;
    vector<ll> new_h(n);
    for (int i = 0; i < n; i++) {
        if (i == 0 || h[i-1].first != h[i].first) {
            new_h[h[i].second] = cur;
            cur++;
        }
        else new_h[h[i].second] = new_h[h[i-1].second];
    }
    vector<ll> a = new_h;
    segtree stree(n+1);
    vector<ll> l(n);
    for (int i = 0; i < n; i++) {
        l[i] = stree.query(1, 1, n, a[i]-1);
        stree.update(1, 1, n, a[i], 1);
    }
    reverse(a.begin(), a.end());
    segtree stree2(n+1);
    vector<ll> r(n);
    for (int i = 0; i < n; i++) {
        r[i] = stree2.query(1, 1, n, a[i]-1);
        stree2.update(1, 1, n, a[i], 1);
    }
    reverse(r.begin(), r.end());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += l[i]*r[i];
    }
    cout << ans << '\n';
    return 0;
}

• 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