Interrogazioni ordinate

La commissione istituita per l’esame di maturità della classe di Luca ha ricevuto dal MIUR l’elenco dei codici SIDI di tutti gli N alunni da esaminare, con il suggerimento che l’ordine delle interrogazioni all’esame orale segua, in ordine crescente, il codice SIDI.
Ciò significa che uno studente i dovrebbe essere interrogato prima di uno studente j se il codice SIDI del primo è inferiore a quello del secondo (ovvero C_i < C_j).
Seguire le indicazioni del Ministero comporterebbe però una certa confusione tra gli studenti, abituati a essere interrogati in ordine per numero crescente di registro (numero 1, numero 2, . . . , numero N).
Assecondando le richieste degli studenti, la commissione stabilisce di adottare la modalità consueta (in ordine per numero crescente di registro), ma vuole prima stabilire qual è l’impatto di questa scelta.
In particolare si vuole stabilire per quante coppie di studenti (i, j) cambierebbe l’ordine di interrogazione, ovvero per quante coppie (i, j) i verrebbe interrogato prima di j con uno dei due metodi ma dopo j con l’altro.

Dati di input

Il file input.txt è composto da 2 righe.

• La prima riga contiene l’intero N, il numero di studenti.
• La seconda riga contiene N interi positivi separati da spazio: i codici SIDI degli alunni dal numero 1 al numero N.

Dati di output

Il file output.txt contiene un singolo intero: il numero di coppie di studenti che cambiano l’ordine relativo di interrogazione tra il primo e il secondo metodo.

Attenzione: la risposta al problema supera, in alcuni casi, 2³².
Se si lavora, ad esempio, in C/C++ è quindi richiesto l’uso del tipo long long al posto di int.

Assunzioni

• 2 ≤ N ≤ 200 000
• 1 ≤ C_i ≤ 10000000 per ogni i=0. . .N−1.
• Il codice SIDI è univoco: C_i ≠ C_j per ogni (i, j) con i ≠ j.

Esempi di input/output

input.txt	output.txt
4 14 63 22 31	2
5 84 31 57 25 66	6

Spiegazione

Nel primo esempio considera le seguenti coppie di studenti il cui ordine cambia tra i due metodi:

• Codici SIDI 63 e 22 (63 > 22), sono rispettivamente i numeri 2 e 3 nel registro (2 < 3).
• Codici SIDI 63 e 31 (63 > 31), sono rispettivamente i numeri 2 e 4 nel registro (2 < 4).

Tutte le altre coppie mantengono la stessa posizione relativa: gli studenti della coppia verranno interrogati nello stesso ordine indipendentemente dal metodo utilizzato.

---

Ottiene il 50% su array non troppo grandi

/*
	www.valcon.it
	ABC - Interrogazioni ordinate
*/
#include
#include
#define NMAX 200000

using namespace std;

long ELENCO[NMAX+1];

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
			
	long N;
	fin >> N;
	for(long i=1; i <= N; i++)	
		fin >> ELENCO[i];
	
	long long int cambi=0;	
	for(long i=1;   i <  N; i++)
	for(long j=i+1; j <= N; j++)
		if(ELENCO[i] > ELENCO[j])
			cambi++;

	fout << cambi;
    return 0;
}