Submission #232869

#	Time	Username	Problem	Language	Result	Execution time	Memory
232869		AlexLuchianov	Mountains (NOI20_mountains)	C++14	100 / 100	529 ms	29500 KiB

Mountains

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <map>

using namespace std;

using ll = long long;

int const nmax = 300000;
ll v[1 + nmax];

map<ll,int> mp;

void normalize(int n){
  vector<ll> temp;
  for(int i = 1;i <= n; i++)
    temp.push_back(v[i]);
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++)
    mp[temp[i]] = 1 + i;
  for(int i = 1;i <= n; i++)
    v[i] = mp[v[i]];
}

class FenwickTree{
private:
  vector<int> aib;
  int n;
public:
  FenwickTree(int n_){
    n = n_;
    aib.resize(1 + n);
  }
  void update(int pos, int val){
    for(int x = pos; x <= n; x += (x ^ (x & (x-1))))
      aib[x] += val;
  }
  int query(int pos){
    int result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result;
  }
};

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> v[i];
  normalize(n);

  FenwickTree basic(n), part(n);
  for(int i = 1;i <= n; i++)
    basic.update(v[i], 1);

  ll result = 0;
  for(int i = 1; i <= n; i++){
    int x = part.query(v[i] - 1);
    result += 1LL * part.query(v[i] - 1) * (basic.query(v[i] - 1) - x);
    part.update(v[i], 1);
  }
  cout << result;
  return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'void normalize(int)':
Mountains.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.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