Submission #1027581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027581		kkkkkkkk	Mountains (NOI20_mountains)	C++14	100 / 100	562 ms	55380 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;

#define int long long

int tree[1200005], a[300005];

void update(int k, int left, int right, int poz) {
    if (left>right||right<poz||left>poz)
        return;
    if (left==right) {
        if (left==poz)
            tree[k]++;
        return;
    }
    int mid=(left+right)/2;
    update(2*k, left, mid, poz);
    update(2*k+1, mid+1, right, poz);
    tree[k]=tree[2*k]+tree[2*k+1];
}

int query(int k, int left, int right, int l, int r) {
    if (right<left||right<l||left>r)
        return 0;
    if (l<=left&&right<=r)
        return tree[k];
    int mid=(left+right)/2;
    int r1=query(2*k, left, mid, l, r);
    int r2=query(2*k+1, mid+1, right, l, r);
    return r1+r2;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    set<int> s;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    map<int,int> compressed;
    int br=0;
    for (auto x:s)
        compressed[x]=br, br++;
    for (int i=0;i<n;i++)
        a[i]=compressed[a[i]];
    update(1, 0, n-1, a[0]);
    int rez1[n]={0}, rez2[n]={0};
    for (int i=1;i<n-1;i++) {
        rez1[i]=query(1, 0, n-1, 0, a[i]-1);
        update(1, 0, n-1, a[i]);
    }
    memset(tree, 0, sizeof(tree));
    update(1, 0, n-1, a[n-1]);
    for (int i=n-2;i>0;i--) {
        rez2[i]=query(1, 0, n-1, 0, a[i]-1);
        update(1, 0, n-1, a[i]);
    }
    int rez=0;
    for (int i=1;i<n-1;i++)
        rez+=rez1[i]*rez2[i];
    cout << rez;

    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