Submission #282495

#	Time	Username	Problem	Language	Result	Execution time	Memory
282495		its_aks_ulure	Mountains (NOI20_mountains)	C++14	100 / 100	1360 ms	44808 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const long long mod = 1e9 + 7;

int n;
long long arr[N];
int segtree[2 * N];
long merge(long x, long y){
    return x + y;
}
void segtree_update(int ind, int val, int n_){
    for(segtree[ind += n_] += val; ind > 1; ind >>= 1)
        segtree[ind >> 1] = merge(segtree[ind], segtree[ind ^ 1]);
}
long segtree_query(int l, int r, int n_){
    long res = 0;
    for(l += n_, r += n_; l < r; l >>= 1, r >>= 1){
        if((l & 1) == 1)
            res = merge(res, segtree[l++]);
        if((r & 1) == 1)
            res = merge(res, segtree[--r]);
    }
    return res;
}
void solve(int test){
    set<long long> s;
    int i = 0;
    for(i = 0; i < n; i++)
        s.insert(arr[i]);
    map<long long, int> mp;
    int x = 0;
    for(long long xx : s)
        mp[xx] = x++;
    vector<int> cnt(n);
    int n_ = s.size();
    for(i = 0; i < n; i++){
        //cout <<
        cnt[i] = segtree_query(0, mp[arr[i]], n_);
        segtree_update(mp[arr[i]], 1, n_);
    }
    memset(segtree, 0, sizeof(segtree));
    long long ans = 0;
    for(i = n - 1; i >= 0; i--){
        ans += cnt[i] * 1LL * segtree_query(0, mp[arr[i]], n_);
        segtree_update(mp[arr[i]], 1, n_);
    }
    cout << ans << "\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    for(int test = 1; test <= t; test++){
        int i = 0;
        cin >> n;
        for(i = 0; i < n; i++)
            cin >> arr[i];
        solve(test);
    }
    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