Submission #372755

#	Time	Username	Problem	Language	Result	Execution time	Memory
372755		SnowFlake7	Mountains (NOI20_mountains)	C++14	100 / 100	378 ms	20204 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;

struct nr {
    long long i,v,idx;
}v[300005];
long long st[300005],dr[300005],aib[300005],n,s;

bool cmp1(nr a, nr b) {
    return a.i < b.i;
}
bool cmp2(nr a, nr b) {
    return a.idx < b.idx;
}
void update(long long a, long long b) {
    for(long long i = a;i <= n;i += (i&(-i)))
        aib[i] += b;
}
long long query(long long a) {
    s = 0;
    for(long long i = a;i > 0;i -= (i&(-i)))
        s += aib[i];
    return s;
}
int main()
{
    long long cnt = 1,ans = 0;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> v[i].i;
        v[i].idx = i;
    }
    sort(v + 1, v + n + 1, cmp1);
    v[1].v = 1;
    for(int i = 2;i <= n;i++) {
        if(i > 1 && v[i].i != v[i - 1].i)
            cnt++;
        v[i].v = cnt;
    }
    sort(v + 1, v + n + 1, cmp2);
    for(int i = 1;i <= n;i++) {
        update(v[i].v, 1);
        st[i] = query(v[i].v - 1);
    }
    for(int i = 1;i <= n;i++)
        update(v[i].v, -1);
    for(int i = n;i >= 1;i--) {
        update(v[i].v, 1);
        dr[i] = query(v[i].v - 1);
        ans += st[i] * dr[i];
    }
    cout << ans;
    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