Submission #227172

#	Time	Username	Problem	Language	Result	Execution time	Memory
227172		TheKingAleks	Mountains (NOI20_mountains)	C++14	100 / 100	981 ms	58892 KiB

Mountains

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const ll MAX_N = 3e5+2;
ll a[MAX_N];
ll res;
set<ll> s;
unordered_map<ll,ll> m;
ll br=1;
vector<ll> tree1(MAX_N*4);
vector<ll> tree2(MAX_N*4);
void update(vector<ll> &tree,ll node,ll tl,ll tr,ll l,ll r)
{
    if(tl > r || tr < l)return;
    if(tl == tr)
    {
        tree[node]++;
        return;
    }
    ll mid = (tl+tr)/2;
    update(tree,node*2,tl,mid,l,r);
    update(tree,node*2+1,mid+1,tr,l,r);
    tree[node] = tree[node*2]+tree[node*2+1];
}
ll query(vector<ll> &tree,ll node,ll tl,ll tr,ll l,ll r)
{
    if(tl > r || tr < l)return 0;
    if(tl >= l && tr <= r)
    {
        return tree[node];
    }
    ll mid = (tl+tr)/2;
    return query(tree,node*2,tl,mid,l,r)+query(tree,node*2+1,mid+1,tr,l,r);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    vector<ll> l(n+2);
    vector<ll> r(n+2);
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
        s.insert(a[i]);
    }
    for(auto &it : s)
    {
        m[it] = br;
        br++;
    }
    br--;
    update(tree1,1,1,br,m[a[0]],m[a[0]]);
    for(ll i=1; i<n; i++)
    {
        l[i] = query(tree1,1,1,br,1,m[a[i]]-1);
        update(tree1,1,1,br,m[a[i]],m[a[i]]);
    }
    update(tree2,1,1,br,m[a[n-1]],m[a[n-1]]);
    for(ll i=n-2; i>=0; i--)
    {
        r[i] = query(tree2,1,1,br,1,m[a[i]]-1);
        update(tree2,1,1,br,m[a[i]],m[a[i]]);
    }
    for(ll i=0;i<n;i++)
    {
        res+=(l[i]*r[i]);
    }
    cout<<res<<endl;

}

• 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