Submission #889136

#	Time	Username	Problem	Language	Result	Execution time	Memory
889136		dimashhh	Mountains (NOI20_mountains)	C++17	100 / 100	266 ms	28656 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 998244353;
typedef long long ll;

ll n,a[N],t[N * 4];
vector<ll> v;
void cl(){
    for(int i = 1;i <= n * 4;i++){
        t[i] =0;
    }
}
void upd(int pos,int v = 1,int tl =1,int tr = n){
    t[v]++;
    if(tl ==tr) return;
    int tm = (tl + tr) >> 1;
    if(pos <= tm) upd(pos,v+v,tl,tm);
    else upd(pos,v+v+1,tm+1,tr);
}
ll get(int l,int r,int v = 1,int tl = 1,int tr =n){
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) >> 1;
    return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
}
ll l[N],res = 0;
void test(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    for(int i = 1;i <= n;i++){
        a[i] = (lower_bound(v.begin(),v.end(),a[i]) - v.begin()) + 1;
        l[i] = get(1,a[i] - 1);
        upd(a[i]);
    }
    cl();
    for(int i = n;i >= 1;i--){
        // cout << get(a[i] + 1,n) << '\n';
        res += l[i] * get(1,a[i] - 1);
        upd(a[i]);
    }
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;//cin >> T;
    while (T--) test();
}

• 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