Submission #692461

#	Time	Username	Problem	Language	Result	Execution time	Memory
692461		saayan007	Mountains (NOI20_mountains)	C++17	100 / 100	123 ms	20052 KiB

Mountains

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

using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb push_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

ll n;
ll lef[300000 + 1];
ll rig[300000 + 1];

ll rsum(ll pos) {
    ll s = 0;
    while(pos >= 1) {
        s += rig[pos];
        pos -= (pos & -pos);
    }
    return s;
}

void rupdate(ll pos, ll val) {
    while(pos <= n) {
        rig[pos] += val;
        pos += (pos & -pos);
    }
}

ll lsum(ll pos) {
    ll s = 0;
    while(pos >= 1) {
        s += lef[pos];
        pos -= (pos & -pos);
    }
    return s;
}

void lupdate(ll pos, ll val) {
    while(pos <= n) {
        lef[pos] += val;
        pos += (pos & -pos);
    }
}

void solve()
{
    cin >> n;
    pl h[n + 1];
    fur(i, 1, n) {
        cin >> h[i].fr;
        h[i].sc = i;
    }
    sort(h + 1, h + n + 1, [&] (pl lef, pl rig) {
        if(lef.fr != rig.fr)
            return lef.fr < rig.fr;
        return lef.sc > rig.sc;
    });
    /* fur(i, 1, n) */
    /*     cout << h[i].fr << ' ' << h[i].sc << nl; */
    /* cout << nl; */
    ll l[n + 1], r[n + 1];
    
    fur(i, 1, n) {
        l[h[i].sc] = lsum(h[i].sc);
        lupdate(h[i].sc, 1);
    }
    /* fur(i, 1, n) */
    /*     cout << l[i] << ' '; */
    /* cout << nl; */
    fur(i, 1, n)
        h[i].sc = n + 1 - h[i].sc;
    sort(h + 1, h + n + 1, [&] (pl lef, pl rig) {
        if(lef.fr != rig.fr)
            return lef.fr < rig.fr;
        return lef.sc > rig.sc;
    });
    /* fur(i, 1, n) */
    /*     cout << h[i].fr << ' ' << h[i].sc << nl; */
    /* cout << nl; */
    fur(i, 1, n) {
        r[n + 1 - h[i].sc] = rsum(h[i].sc);
        rupdate(h[i].sc, 1);
    }
    /* fur(i, 1, n) */
    /*     cout << r[i] << ' '; */
    /* cout << nl; */

    ll ans = 0;
    fur(i, 1, n) {
        ans += l[i] * r[i];
    }
    cout << ans << nl;
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

	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