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 BR 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]++;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5
1 5 2 4 3

Output

x
+
cmd
4

#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;
}

Copy The Code & Try With Live Editor

Input

x
+
cmd
5
1 5 2 4 3

Output

x
+
cmd
4
Advertisements

Demonstration


Previous
#2399 Beecrowd Online Judge Solution 2399 Campo Minado Solution in C, C++, Java, Js and Python
Next
#2401 Beecrowd Online Judge Solution 2401 Calculadora Solution in C, C++, Java, Js and Python