Submission #1000759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000759		fryingduc	Mountains (NOI20_mountains)	C++17	100 / 100	142 ms	14684 KiB

Mountains

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

const int maxn = 3e5 + 6;
int n;
long long a[maxn];
int bit[maxn];
int ord[maxn];

#define gb(x) (x) & (-x)
void update(int x, int val) {
    for(int i = x; i <= n; i += gb(i)) bit[i] += val;
}
int get(int x) {
    int ans = 0;
    for(int i = x; i > 0; i -= gb(i)) ans += bit[i];
    return ans;
}
int get(int l, int r) {
    return get(r) - get(l - 1);
}
void solve() {
    cin >> n;
    vector<long long> vec;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        vec.push_back(a[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int i = 1; i <= n; ++i) {
        a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
    }
    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool {
        return a[x] < a[y];
    });
    long long ans = 0;
    for(int i = 1; i <= n; ++i) {
        int cur = 0;
        while(i + cur <= n and a[ord[i]] == a[ord[i + cur]]) ++cur;
        for(int j = i; j < i + cur; ++j) {
            int x = get(ord[j] - 1), y = get(ord[j] + 1, n);
            ans = ans + 1ll * x * y;
            
        }
        for(int j = i; j < i + cur; ++j) {
            update(ord[j], 1);
        }
        i = i + cur - 1;
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    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