Submission #285473

#	Time	Username	Problem	Language	Result	Execution time	Memory
285473		keta_tsimakuridze	Mountains (NOI20_mountains)	C++14	100 / 100	557 ms	14864 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
long long tree[N],h[N],ans,b[N],k,i,bef,n,ind[N];
pair<long long,long long>a[N];
void update(int ind,int val){
           
           for(ind;ind<=i;ind+=ind&(-ind)){
                      tree[ind]+=val;
           }
}
int getans(int ind){
           int pas=0;
           for(ind;ind>=1;ind-=ind&(-ind)){
                     pas+=tree[ind]; 
           }
           return pas;
}
int main(){
           cin>>n; 
           for(k=1;k<=n;k++){
                      cin>>h[k];
                      a[k].first=h[k];
                      a[k].second=k;
           }
           sort(a+1,a+n+1); bef=-1;
           for(k=1;k<=n;k++){
                      if(a[k].first!=bef){
                          bef=a[k].first;
                          i++;
                      }
                      ind[a[k].second]=i;
           }
           for(k=1;k<=n;k++){ 
                      update(ind[k],1);
                     if(ind[k]!=1) b[k]=getans(ind[k]-1);
                    // cout<<k<<" "<<b[k]<<endl;
           }
            for(k=1;k<=n;k++){
                      update(ind[k],-1);
           }
           for(k=n;k>=1;k--){
                      update(ind[k],1);
                      if(ind[k]!=1)ans+=b[k]*(getans(ind[k]-1));
           }
           cout<<ans;
           
           
}

Compilation message (stderr)

Mountains.cpp: In function 'void update(int, int)':
Mountains.cpp:8:16: warning: statement has no effect [-Wunused-value]
    8 |            for(ind;ind<=i;ind+=ind&(-ind)){
      |                ^~~
Mountains.cpp: In function 'int getans(int)':
Mountains.cpp:14:16: warning: statement has no effect [-Wunused-value]
   14 |            for(ind;ind>=1;ind-=ind&(-ind)){
      |                ^~~

• 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