Submission #390304

#	Time	Username	Problem	Language	Result	Execution time	Memory
390304		KrisjanisP	Mountains (NOI20_mountains)	C++14	100 / 100	1000 ms	31688 KiB

Mountains

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;

typedef pair<ll, ll> pii;

const ll N_mx = 3e5;
ll N;
ll H[N_mx];
ll H_c[N_mx];//compressed H

struct Segment{
    ll i;
    ll l, r;
};

class Tree{
public:
    Tree(ll _n){
        n = _n;
        t.resize(4*n,0);
    }
    void update(ll i, ll v){
        updateSegment(rootSegment(), i, v);
    }
    ll sum(ll l, ll r){
        return sumSegment(rootSegment(), l, r);
    }
private:
    ll n;
    vector<ll> t;
    Segment rootSegment(){
        Segment res;
        res.i = 1;
        res.l = 0;
        res.r = n-1;
        return res;
    }
    Segment getLeft(Segment pos){
        return {
            i: pos.i*2,
            l: pos.l,
            r: (pos.l+pos.r)/2
        };
    }
    Segment getRight(Segment pos){
        return {
            i: pos.i*2 + 1,
            l: (pos.l+pos.r)/2 + 1,
            r: pos.r
        };
    }
    void updateSegment(Segment pos, ll i, ll v){
        if(i<pos.l||i>pos.r) return;
        t[pos.i] += v;
        if(pos.l==pos.r) return;
        updateSegment(getLeft(pos), i, v);
        updateSegment(getRight(pos), i, v);
    }
    ll sumSegment(Segment pos, ll l, ll r){
        if(pos.l>=l&&pos.r<=r) return t[pos.i];
        if(pos.l>r||pos.r<l) return 0;
        ll sum_left = sumSegment(getLeft(pos), l, r);
        ll sum_right = sumSegment(getRight(pos), l, r);
        return sum_left+sum_right;
    }
};

void input(){
    cin>>N;
    for(ll i=0;i<N;i++)
        cin>>H[i];
}

void solve(){
    pii H2[N];
    for(ll i=0;i<N;i++){
        H2[i] = {H[i], i};
    }
    sort(H2, H2+N);
    ll id=0;
    for(ll i=0;i<N;i++){
        if(i&&H2[i].f>H2[i-1].f) id++; 
        H[H2[i].s] = id;
    }
    Tree left(N_mx);
    Tree right(N_mx);
    for(ll i=0;i<N;i++){
        right.update(H[i], 1);
    }
    ll res = 0;
    for(ll i=0;i<N;i++){
        //process this position...
        //1) remove from right at this position
        //2) process this position
        //3) add to left at this position
        right.update(H[i], -1);
        if(H[i]!=0){
            ll res_l = left.sum(0, H[i]-1);
            ll res_r = right.sum(0, H[i]-1);
            res += res_l*res_r;
        }
        left.update(H[i], 1);
    }
    cout<<res;
}

int main(){
    input();
    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