oj.uz

Submission #347706

# Submission time Handle Problem Language Result Execution time Memory
347706 2021-01-13T10:34:47 Z Pety Mountains (NOI20_mountains) C++14
24 / 100
 206 ms 8048 KB 
#include <bits/stdc++.h>

using namespace std;

const int N= 3e5 + 2;
int n, a[N], aib[N], st[N], dr[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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1516 KB Output is correct
2 Correct 49 ms 6252 KB Output is correct
3 Correct 50 ms 6252 KB Output is correct
4 Correct 50 ms 6380 KB Output is correct
5 Correct 49 ms 6252 KB Output is correct
6 Correct 49 ms 6252 KB Output is correct
7 Correct 52 ms 6252 KB Output is correct
8 Correct 49 ms 6252 KB Output is correct
9 Correct 50 ms 6252 KB Output is correct
10 Correct 50 ms 6380 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6872 KB Output is correct
2 Correct 95 ms 6764 KB Output is correct
3 Correct 98 ms 6812 KB Output is correct
4 Correct 96 ms 6764 KB Output is correct
5 Correct 97 ms 6740 KB Output is correct
6 Correct 96 ms 6764 KB Output is correct
7 Correct 94 ms 6764 KB Output is correct
8 Correct 90 ms 6892 KB Output is correct
9 Correct 91 ms 6820 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6872 KB Output is correct
2 Correct 95 ms 6764 KB Output is correct
3 Correct 98 ms 6812 KB Output is correct
4 Correct 96 ms 6764 KB Output is correct
5 Correct 97 ms 6740 KB Output is correct
6 Correct 96 ms 6764 KB Output is correct
7 Correct 94 ms 6764 KB Output is correct
8 Correct 90 ms 6892 KB Output is correct
9 Correct 91 ms 6820 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 135 ms 7020 KB Output is correct
12 Correct 137 ms 7020 KB Output is correct
13 Correct 139 ms 7020 KB Output is correct
14 Correct 136 ms 7148 KB Output is correct
15 Correct 134 ms 7020 KB Output is correct
16 Correct 135 ms 7020 KB Output is correct
17 Correct 142 ms 7276 KB Output is correct
18 Correct 91 ms 7020 KB Output is correct
19 Correct 90 ms 7068 KB Output is correct
20 Correct 2 ms 1516 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6872 KB Output is correct
2 Correct 95 ms 6764 KB Output is correct
3 Correct 98 ms 6812 KB Output is correct
4 Correct 96 ms 6764 KB Output is correct
5 Correct 97 ms 6740 KB Output is correct
6 Correct 96 ms 6764 KB Output is correct
7 Correct 94 ms 6764 KB Output is correct
8 Correct 90 ms 6892 KB Output is correct
9 Correct 91 ms 6820 KB Output is correct
10 Correct 1 ms 1516 KB Output is correct
11 Correct 135 ms 7020 KB Output is correct
12 Correct 137 ms 7020 KB Output is correct
13 Correct 139 ms 7020 KB Output is correct
14 Correct 136 ms 7148 KB Output is correct
15 Correct 134 ms 7020 KB Output is correct
16 Correct 135 ms 7020 KB Output is correct
17 Correct 142 ms 7276 KB Output is correct
18 Correct 91 ms 7020 KB Output is correct
19 Correct 90 ms 7068 KB Output is correct
20 Correct 2 ms 1516 KB Output is correct
21 Correct 201 ms 7916 KB Output is correct
22 Correct 202 ms 7900 KB Output is correct
23 Correct 188 ms 7916 KB Output is correct
24 Correct 194 ms 8048 KB Output is correct
25 Correct 190 ms 7916 KB Output is correct
26 Correct 206 ms 7916 KB Output is correct
27 Correct 199 ms 8044 KB Output is correct
28 Correct 131 ms 7916 KB Output is correct
29 Correct 134 ms 7888 KB Output is correct
30 Correct 1 ms 1516 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1516 KB Output is correct
2 Correct 49 ms 6252 KB Output is correct
3 Correct 50 ms 6252 KB Output is correct
4 Correct 50 ms 6380 KB Output is correct
5 Correct 49 ms 6252 KB Output is correct
6 Correct 49 ms 6252 KB Output is correct
7 Correct 52 ms 6252 KB Output is correct
8 Correct 49 ms 6252 KB Output is correct
9 Correct 50 ms 6252 KB Output is correct
10 Correct 50 ms 6380 KB Output is correct
11 Correct 99 ms 6872 KB Output is correct
12 Correct 95 ms 6764 KB Output is correct
13 Correct 98 ms 6812 KB Output is correct
14 Correct 96 ms 6764 KB Output is correct
15 Correct 97 ms 6740 KB Output is correct
16 Correct 96 ms 6764 KB Output is correct
17 Correct 94 ms 6764 KB Output is correct
18 Correct 90 ms 6892 KB Output is correct
19 Correct 91 ms 6820 KB Output is correct
20 Correct 1 ms 1516 KB Output is correct
21 Correct 135 ms 7020 KB Output is correct
22 Correct 137 ms 7020 KB Output is correct
23 Correct 139 ms 7020 KB Output is correct
24 Correct 136 ms 7148 KB Output is correct
25 Correct 134 ms 7020 KB Output is correct
26 Correct 135 ms 7020 KB Output is correct
27 Correct 142 ms 7276 KB Output is correct
28 Correct 91 ms 7020 KB Output is correct
29 Correct 90 ms 7068 KB Output is correct
30 Correct 2 ms 1516 KB Output is correct
31 Incorrect 1 ms 1516 KB Output isn't correct
32 Halted 0 ms 0 KB -