Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BALE11 - Balé

 

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, 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.

Restrições

  • 1 ≤ N ≤ 100 000.
  • Todas as dançarinas possuirão níveis distintos, entre 1 e 100 000.
  • O total de pares válidos, em todos os casos, será ≤ 1 000 000.

Exemplos

Entrada
5
1 5 2 4 3

Saída
4

Entrada
9
9 8 7 6 5 4 3 1 2

Saída
35


Adicionado por:Wanderley Guimarăes
Data:2012-03-10
Tempo limite:0.100s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2011 - fase 2 nível 1

hide comments
2017-02-04 17:06:25
Passa em o(n²) com insertionsort
2014-01-24 11:22:24 Yuri Siqueira [UFCG]
[dica] :D
Passa com NlogN, se pensar um pouquinho da pra sacar que o numero de pares seria o numero de pares totais do caso perfeito menos o numero de trocas que um mergeSorte faria...
2013-10-20 03:16:07 Tiago Nápoli
Só passa com n log n, então a dica é usar estrutura de dados BIT ou mergesort
2012-03-16 03:15:43 Marcos Kawakami
Algoritmos quadráticos năo văo passar no tempo nem com otimizaçăo (ou talvez até passem, mas a princípio nao deveriam). O tempo das soluçőes é alto porque o SPOJ soma os tempos de todos casos de teste, além de ser bem lento.

Last edit: 2012-11-10 13:40:23
2012-03-16 03:02:20 Severino Mizael da silva
assim fica complicado a melhor soluçăo ta passando com 2.12 segundos e o time aqui e de apenas 1, meu algoritimos e N^2 porem está muito otimizado
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.