Submission #1263422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263422		sohamsen15	Mountains (NOI20_mountains)	C++20	100 / 100	328 ms	38024 KiB

Mountains

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {
    ll n;
    vector<ll> B1, B2;

    BIT(ll n) : n(n), B1(n + 1, 0), B2(n + 1, 0) {}

    void update(vector<ll>& B, ll i, ll v) {
        for (; i <= n; i += i & -i) B[i] += v;
    }

    void range_update(ll l, ll r, ll v) {
        // add v to range [l, r]
        update(B1, l, v);
        update(B1, r + 1, -v);
        update(B2, l, v * (l - 1));
        update(B2, r + 1, -v * r);
    }

    ll query(const vector<ll>& B, ll i) {
        ll res = 0;
        for (; i > 0; i -= i & -i) res += B[i];
        return res;
    }

    ll prefix_sum(ll i) {
        return query(B1, i) * i - query(B2, i);
    }

    ll range_sum(ll l, ll r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(0);

    ll n, curr = 1; cin >> n;
    vector<ll> a(n + 1); for (ll i = 1; i <= n; i++) cin >> a[i];
    vector<ll> ac(n + 1, -999); for (ll i = 1; i <= n; i++) ac[i] = a[i]; sort(ac.begin(), ac.end());
    map<ll, ll> coord; for (auto x: ac) if (!coord.count(x)) coord[x] = curr++;
    for (ll i = 1; i <= n; i++) a[i] = coord[a[i]];
    vector<ll> less(n + 1); BIT lessbit(n + 1); 
    for (ll i = 1; i <= n; i++) less[i] = lessbit.range_sum(0, a[i] - 1), lessbit.range_update(a[i], a[i], 1);
    vector<ll> lessr(n + 1); BIT lessrbit(n + 1);
    for (ll i = n; i >= 1; i--) lessr[i] = lessrbit.range_sum(0, a[i] - 1), lessrbit.range_update(a[i], a[i], 1);
    ll ans = 0; for (ll i = 1; i <= n; i++) ans += less[i] * lessr[i];
    cout << ans;
}

• 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