Submission #285472

#	Time	Username	Problem	Language	Result	Execution time	Memory
285472		mosiashvililuka	Mountains (NOI20_mountains)	C++14	100 / 100	659 ms	34168 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,lf[300009],rg[300009],f[300009],fen[300009],pas;
map <long long, long long> m;
map <long long, long long>::iterator it;
void upd(long long q){
    while(q<=a+1){
        fen[q]++;
        q=q+(q&(-q));
    }
}
long long read(long long q){
    long long jm=0;
    while(q>=1){
        jm+=fen[q];
        q=q-(q&(-q));
    }
    return jm;
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(i=1; i<=a; i++){
        cin>>f[i];
        m[f[i]]=1;
    }
    zx=0;
    for(it=m.begin(); it!=m.end(); it++){
        zx++;
        m[(*it).first]=zx;
    }
    for(i=1; i<=a; i++) f[i]=m[f[i]];
    for(i=0; i<=a+2; i++) fen[i]=0;
    for(i=1; i<=a; i++){
        lf[i]=read(f[i]-1);
        upd(f[i]);
    }
    for(i=0; i<=a+2; i++) fen[i]=0;
    for(i=a; i>=1; i--){
        rg[i]=read(f[i]-1);
        upd(f[i]);
    }
    for(i=1; i<=a; i++){
        pas+=lf[i]*rg[i];
    }
    cout<<pas;
    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