Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2400
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2400
Balé
Por OBI - Olimpíada Brasileira de Informática 2011 
Brazil
Timelimit: 1
Uma academia de balé irá organizar uma Oficina de Balé Intensivo (OBI) na Semana de Balé Contemporâneo (SBC). Nessa academia, existem N bailarinas que praticam regularmente. O dono da academia, por ser experiente, consegue medir o nível de habilidade de cada uma delas por um número inteiro; nessa medição, números maiores correspondem a dançarinas mais habilidosas, e os números obtidos são todos distintos. Além disso, ele possui uma lista das bailarinas em ordem cronológica de ingresso na academia: As bailarinas que aparecem primeiro na lista estão há mais tempo na academia, e as que estão no final ingressaram mais recentemente.
O dono da academia decidiu escolher duas das bailarinas para ajudá-lo na realização do evento: uma ajudará no trabalho braçal, enquanto a outra irá exemplificar os passos de balé. Por seu perfeccionismo, ele deseja que a bailarina que exemplificará os passos de dança seja, dentre as duas meninas do par, a mais habilidosa e a que frequenta a academia há mais tempo.
Ele sabe que a Oficina será um sucesso desde que os dois critérios mencionados acima sejam satisfeitos pela dupla de dançarinas escolhidas. Com isso, ele ficou curioso para saber quantas duplas de dançarinas podem ajudá-lo na Oficina. A quantidade de dançarinas, contudo, é relativamente grande e ele não possui nem tempo nem paciência para fazer tal cálculo. Como vocês são amigos, ele pediu a sua ajuda para contar quantas duplas são válidas. Você pode ajudá-lo?
Por exemplo, digamos que a academia possua 5 dançarinas com níveis de habilidade 1, 5, 2, 4 e 3, onde a primeira, que possui nível "1", está na academia há mais tempo e a última, que possui nível "3", está há menos. Temos, então, 4 possíveis duplas que poderemos usar nesta Oficina, que são (5, 2),(5, 4),(5, 3) e (4, 3). Note que a dupla (1, 3), por exemplo, não pode ser escolhida pelo dono da academia, pois a mais habilidosa dentre as duas é também a mais nova da dupla.
Entrada
A primeira linha contém um número N (1 ≤ N ≤ 100 000), que representa a quantidade de dançarinas que estão registradas na academia. A segunda linha da entrada contém N inteiros, onde o primeiro inteiro é o nível da dançarina que está há mais tempo na academia, o segundo inteiro é o nível da próxima dançarina mais antiga na academia (mas mais nova que a dançarina anterior), e assim sucessivamente.
Saída
A saída consistirá num único número X, que representa o total de duplas de dançarinas válidas para essa Oficina, dadas as regras descritas anteriormente.
| Exemplos de Entrada | Exemplos de Saída |
|
5 1 5 2 4 3 |
4 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#define true 1
#define false 0
#define MAXSIZE 100100
int bit[MAXSIZE + 10];
int get(int);
int update(int);
int main (void)
{
int n, i, tmp;
scanf("%d", &n);
memset(bit, 0, sizeof(bit));
long long ans = 0;
for (i = 0; i < n; ++i)
{
scanf("%d", &tmp);
update(tmp);
ans += get(MAXSIZE) - get(tmp);
}
printf("%lld\n", ans);
}
int get(int x)
{
int retorno = 0;
for (; x; x -= x&-x)
retorno += bit[x];
return retorno;
}
int update(int x)
{
for (; x < MAXSIZE; x += x&-x)
bit[x]++;
}
Input
1 5 2 4 3
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 100010
#define MAXS 1000010
#define max(A, B) (A) > (B) ? (A) : (B)
#define LSOne(S) (S & (-S))
int MAX = 1000001, bits[MAXS], n, skill[MAXN], answer, maximum;
void update(int x) {
while (x < 100005) {
bits[x]++;
x += LSOne(x);
}
}
int sum(int x) {
int s = 0;
while (x > 0) {
s += bits[x];
x -= LSOne(x);
}
return s;
}
int main() {
scanf("%d", &n);
for (int i = 1; i < = n; i++) {
scanf("%d", &skill[i]);
maximum = max(maximum, skill[i]);
}
for (int i = 1; i < = n; i++) {
update(skill[i]);
answer += sum(maximum) - sum(skill[i]);
}
printf("%d\n", answer);
return 0;
}
Input
1 5 2 4 3
Output