Submission #340308

#	Time	Username	Problem	Language	Result	Execution time	Memory
340308		apostoldaniel854	Mountains (NOI20_mountains)	C++14	100 / 100	611 ms	29548 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

int n;

const int MAX_N = 3e5;
int aibL[1 + MAX_N], aibR[1 + MAX_N];
ll h[1 + MAX_N];

void upd (int pos, int val, int aib[]) {
    while (pos <= n) {
        aib[pos] += val;
        pos += pos & -pos;
    }
}
int qry (int pos, int aib[]) {
    int ans = 0;
    while (pos) {
        ans += aib[pos];
        pos -= pos & -pos;
    }
    return ans;
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> n;
    map <ll, int> mp;
    for (int i = 1; i <= n; i++)
        cin >> h[i], mp[h[i]];
    int nr = 0;
    for (auto &x : mp)
        x.second = ++nr;
    for (int i = 1; i <= n; i++)
        h[i] = mp[h[i]];
    for (int i = 2; i <= n; i++)
        upd (h[i], 1, aibR);
    upd (h[1], 1, aibL);
    ll ans = 0;
    for (int i = 2; i <= n; i++) {
        upd (h[i], -1, aibR);
        ans += 1ll * qry (h[i] - 1, aibL) * qry (h[i] - 1, aibR);
        upd (h[i], 1, aibL);
    }
    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