Submission #267040

#	Time	Username	Problem	Language	Result	Execution time	Memory
267040		kimbj0709	Mountains (NOI20_mountains)	C++14	100 / 100	182 ms	14172 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 300050
vector<int> fenwick(maxn,0);
void add(int b,int c){
  int temp = b+1;
  while(temp<=fenwick.size()){
    fenwick[temp] += c;
    temp += temp & (-temp);
  }
}
int getsum(int a,int b){
  int temp = b+1;
  int total = 0;
  while(temp!=0){
    total += fenwick[temp];
    temp -= temp & (-temp);
  }
  int idk = a;
  while(idk!=0){
    total -= fenwick[idk];
    idk -= idk & (-idk);
  }
  return total;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_input;
  int input;
  vector<int> vect1;
  vector<int> vect2;
  cin >> no_of_input;
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    vect1.push_back(input);
    vect2.push_back(input);
  }
  sort(vect2.begin(),vect2.end());
  for(int i=0;i<no_of_input;i++){
    int k = lower_bound(vect2.begin(),vect2.end(),vect1[i])-vect2.begin();
    vect1[i] = k+1;
  }
  for(int i=0;i<vect1.size();i++){
    vect2[i] = getsum(0,vect1[i]-1);
    add(vect1[i],1);
  }
  for(int i=0;i<fenwick.size();i++){
    fenwick[i] = 0;
  }
  int ans = 0;
  for(int i=vect1.size()-1;i>=0;i--){
    ans += vect2[i]*getsum(0,vect1[i]-1);
    add(vect1[i],1);
  }
  cout << ans;

}

Compilation message (stderr)

Mountains.cpp: In function 'void add(long long int, long long int)':
Mountains.cpp:8:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |   while(temp<=fenwick.size()){
      |         ~~~~^~~~~~~~~~~~~~~~
Mountains.cpp: In function 'int32_t main()':
Mountains.cpp:45:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i=0;i<vect1.size();i++){
      |               ~^~~~~~~~~~~~~
Mountains.cpp:49:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0;i<fenwick.size();i++){
      |               ~^~~~~~~~~~~~~~~

• 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