Submission #347710

#	Time	Username	Problem	Language	Result	Execution time	Memory
347710		Pety	Mountains (NOI20_mountains)	C++14	100 / 100	341 ms	14188 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;

const int N= 3e5 + 2;
int n, aib[N], st[N], dr[N];
long long a[N], b[N];

void norm () {
  for (int i = 1; i <= n; i++)
    b[i] = a[i];
  sort(b + 1, b + n + 1);
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}

int query (int x) {
  int s = 0;
  for (int i = x; i; i -= (i & -i))
    s += aib[i];
  return s;
}

void update (int x) {
  for (int i = x; i <= n; i += (i & -i))
    aib[i] += 1;
}

int main ()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  norm();
  for (int i = 1; i <= n; i++) {
    st[i] = query(a[i] - 1);
    update(a[i]);
  }
  long long ans = 0;
  memset(aib, 0, sizeof(aib));
  for (int i = n; i >= 1; i--) {
    dr[i] = query(a[i]  -1);
    update(a[i]);
    ans += 1ll * st[i] * dr[i];
  }
  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