Submission #670934

#	Time	Username	Problem	Language	Result	Execution time	Memory
670934		zeroesandones	Mountains (NOI20_mountains)	C++17	100 / 100	560 ms	42368 KiB

Mountains

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> iset;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb push_back

struct SegTree {
    vi tree;
    ll id;
    ll n;

    SegTree(int N) {
        init(N, 0);
    }

    SegTree(int N, int x) {
        init(N, x);
    }

    void init(int N, int x) {
        id = x;
        n = N;
        while(__builtin_popcountll(n) != 1) ++n;
        tree.resize(2 * n, id);
    }

    void update(ll x, ll k) {
        k += n;
        tree[k] += x;

        for(k /= 2; k >= 1; k /= 2) {
            tree[k] = comb(tree[2 * k], tree[2 * k + 1]);
        }
    }

    ll query(int a, int b, int x, int y, int k) {
        if(a > y || b < x) return id;
        if(a <= x && y <= b) return tree[k];

        int d = (x + y) / 2;
        return comb(query(a, b, x, d, 2 * k), query(a, b, d + 1, y, 2 * k + 1));
    }

    ll query(int a, int b) {
        return query(a, b, 0, n - 1, 1);
    }

    ll comb(ll lhs, ll rhs) {
        return lhs + rhs;
    }

    void print() {
        FOR(i, 1, 2 * n) {
            cout << i << " : " << tree[i] << nl;
        }
    }
};

void solve()
{
    ll n;
    cin >> n;

    ll a[n];
    FOR(i, 0, n)
        cin >> a[i];

    ll b[n];
    FOR(i, 0, n)
        b[i] = a[i];
    sort(b, b + n);
    map<ll, ll> m;
    ll curr = 1;
    FOR(i, 0, n) {
        if(m.find(b[i]) == m.end()) {
            m[b[i]] = curr++;
        }
    }

    FOR(i, 0, n) {
        a[i] = m[a[i]];
    }

    SegTree sgt(n + 1);
    ll left[n], right[n];
    FOR(i, 0, n) {
        left[i] = sgt.query(0, a[i] - 1);
        sgt.update(1, a[i]);
    }

    FOR(i, 0, n) {
        sgt.update(-1, a[i]);
    }

    FORD(i, n - 1, 0) {
        right[i] = sgt.query(0, a[i] - 1);
        sgt.update(1, a[i]);
    }

    ll ans = 0;
    FOR(i, 0, n) {
        ans += left[i] * right[i];
    }

    cout << ans << nl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

• 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