Submission #345624

#	Time	Username	Problem	Language	Result	Execution time	Memory
345624		Matteo_Verz	Mountains (NOI20_mountains)	C++17	100 / 100	216 ms	15468 KiB

Mountains

/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <random>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

const int INF = 2e9;
const int N = 3e5;

class Fenwick {
  private:
    vector <int> a;

    int lsb(int i) {
      return (i & (-i));
    }

  public:
    Fenwick(int n) {
      a.resize(1 + n);
    }

    void Update(int pos, int value) {
      for(int i = pos; i < a.size(); i += lsb(i))
        a[i] += value;
    }

    int Query(int pos) {
      int ans(0);
      for(int i = pos; i > 0; i -= lsb(i))
        ans += a[i];

      return ans;
    }
};

struct ura {
  int idx;
  long long init, val;
};
ura v[1 + N];

bool SortVal(ura a, ura b) {
  return a.init < b.init;
}

bool SortIdx(ura a, ura b) {
  return a.idx < b.idx;
}

void Normalize(int n) {
  int last(1);
  sort(v + 1, v + n + 1, SortVal);
  v[1].val = last;

  for(int i = 2; i <= n; i++) {
    if(v[i].init != v[i - 1].init) ++last;
    v[i].val = last;
  }

  sort(v + 1, v + n + 1, SortIdx);
}

int main() {
  int n;
  long long ans(0);
  scanf("%d", &n);

  for(int i = 1; i <= n; i++) {
    scanf("%lld", &v[i].init);
    v[i].idx = i;
  }

  Normalize(n);
  
  Fenwick aibl(n), aibr(n);
  for(int i = n; i >= 1; i--)
    aibr.Update(v[i].val, 1);

  for(int i = 1; i <= n; i++) {
    aibr.Update(v[i].val, -1);
    aibl.Update(v[i].val, 1);

    ans += 1LL * aibr.Query(v[i].val - 1) * aibl.Query(v[i].val - 1);
  }

  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

Mountains.cpp: In member function 'void Fenwick::Update(int, int)':
Mountains.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       for(int i = pos; i < a.size(); i += lsb(i))
      |                        ~~^~~~~~~~~~
Mountains.cpp: In function 'int main()':
Mountains.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Mountains.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |     scanf("%lld", &v[i].init);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

• 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