Fişierul intrare/ieşire:snpid.in, snpid.outSursăLot Resița 2012 - Baraj 2 Seniori
AutorMugurel Ionut AndreicaAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.8 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Snpid

Se dau N puncte în plan, numerotate de la 1 la N. Punctul i are coordonatele (i, y(i)), iar cele N coordonate y formează o permutare a numerelor de la 1 la N. Un dreptunghi frumos este un dreptunghi ce are în colţurile stânga-jos şi dreapta-sus două dintre cele N puncte. Mai exact, două puncte i şi j determină un dreptunghi frumos cu colţul stânga-jos în punctul i şi colţul dreapta-sus în punctul j dacă i < j şi y(i) < y(j). Fie NPID(i, j) numărul de puncte aflate strict în interiorul dreptunghiului frumos cu colţul stânga-jos în punctul i şi colţul dreapta-sus în punctul j.

Cerinţă

Determinaţi pentru fiecare punct i valoarea SNPID(i) = suma tuturor valorilor NPID(i, j) posibile (adică suma numerelor de puncte aflate în interiorul dreptunghiurilor frumoase cu colţul stânga-jos în punctul i).

Date de intrare

Pe prima linie a fişierului snpid.in se afla numărul natural N, reprezentând numărul de puncte. Pe următoarea linie se află N numere naturale, valorile y(1), y(2), ..., y(N) în această ordine.

Date de ieşire

Fişierul snpid.out va conţine N linii, ce-a de-a i-a linie conţinând valoarea SNPID(i).

Restricţii

  • 1 ≤ N ≤ 100 000
  • Atenţie! Rezultatele pot depăşi tipurile de date întregi pe 32 de biţi.

Exemplu

snpid.insnpid.out
12
3 1 4 11 7 12 2 9 10 5 8 6
16
21
8
0
1
0
3
0
0
0
0
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content