Submission #1276230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276230		nanaseyuzuki	Mountains (NOI20_mountains)	C++20	100 / 100	288 ms	29780 KiB

Mountains

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 3e5 + 5, inf = 1e9;

int n, a[mn];

int st[4 * mn];
vector <int> pos[mn];

void update(int id, int l, int r, int pos){
    if(l > pos || r < pos) return;
    if(l == r){
        st[id] ++;
        return;
    }
    int mid = (l + r) >> 1;
    update(2 * id, l, mid, pos);
    update(2 * id + 1, mid + 1, r, pos);
    st[id] = st[2 * id] + st[2 * id + 1];
}

int get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 0;
    if(l >= u && r <= v) return st[id];
    int mid = (l + r) >> 1;
    return get(2 * id, l, mid, u, v) + get(2 * id + 1, mid + 1, r, u, v);
}

void solve(){
    cin >> n;
    int res = 0;
    vector <int> reina;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        reina.push_back(a[i]);
    }
    sort(all(reina)); reina.erase(unique(all(reina)), reina.end());
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(reina.begin(), reina.end(), a[i]) - reina.begin() + 1;
        pos[a[i]].push_back(i);
    }
    for(int p = 1; p <= reina.size(); p++){
        for(auto i : pos[p]) res += get(1, 1, n, 1, i) * get(1, 1, n, i, n);
        for(auto i : pos[p]) update(1, 1, n, i);
    }
    cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

• 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