Submission #369989

#	Time	Username	Problem	Language	Result	Execution time	Memory
369989		ivan_tudor	Mountains (NOI20_mountains)	C++14	100 / 100	271 ms	11884 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
const int N = 3*1e5 + 5;
int aib[N];
void update(int poz,int val){
  for(int i= poz; i< N; i += i&(-i))
    aib[i] += val;
}
int query(int poz){
  int rsp =0 ;
  for(int i = poz; i>0; i-= i&(-i))
    rsp += aib[i];
  return rsp;
}
struct evenim{
  long long h;
  int poz;
  bool operator <(evenim other) const{
    return h < other.h;
  }
};
evenim v[N];
int main()
{
  int n;
  cin>>n;
  for(int i= 1; i<=n;i++){
    long long h;
    cin>>h;
    v[i] = {h, i};
  }
  sort(v+1, v+n+1);
  long long ans = 0;
  for(int i=1; i<=n;){
    int j = i;
    ans += 1LL * query(v[j].poz - 1) * (query(n) - query(v[j].poz));
    while(j + 1<=n && v[j + 1].h == v[i].h){
      j++;
      ans += 1LL * query(v[j].poz - 1) * (query(n) - query(v[j].poz));
    }
    for(int k = i; k<=j;k++){
      update(v[k].poz, 1);
    }
    i = j + 1;
  }
  cout<<ans;
  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