Submission #1164249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164249		ChottuF	Mountains (NOI20_mountains)	C++20	100 / 100	266 ms	24480 KiB

Mountains

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

#define int long long

vector<int> tree;
int cfr = 1;

int sum(int a, int b){
    a += cfr;
    b += cfr;
    int s = 0;
    while (a <= b){
        if (a%2 == 1){
            s += tree[a++];
        }
        if (b%2 == 0){
            s += tree[b--];
        }
        a /= 2;
        b /= 2;
    }
    return s;
}

void update(int k, int x){
    k += cfr;
    tree[k] += x;
    k /= 2;
    while (k >= 1){
        tree[k] = tree[2*k] + tree[2*k+1];
        k /= 2;
    }
}

signed main() {
    int n;
    cin >> n;
    pair<int,int> arr[n];
    for (int i = 0; i<n; i++){
        int a;
        cin >> a;
        arr[i] = {a,i};
    }
    sort(arr,arr+n);
    vector<int> nw(n);
    for (int i = 0; i<n; i++){
        if (i == 0){
            nw[arr[i].second] = cfr;
        }
        else if (arr[i].first == arr[i-1].first){
            nw[arr[i].second] = cfr;
        }
        else{
            nw[arr[i].second] = ++cfr;
        }
    }
    cfr++;
    vector<int> a(cfr);
    while (__builtin_popcount(cfr) != 1){
        a.push_back(0);
        cfr++;
    }
    tree.resize(2*cfr);
    vector<int> lft(n), rgt(n);
    for (int i = 0; i<n; i++){
        lft[i] = sum(0,nw[i]-1);
        update(nw[i],1);
    }
    tree.clear();
    tree.resize(2*cfr);
    for (int i = n-1; i>=0; i--){
        rgt[i] = sum(0,nw[i]-1);
        update(nw[i],1);
    }
    int ans = 0;
    for (int i = 0; i<n; i++){
        ans += lft[i]*rgt[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