Considerăm un şir de numere a₁, a₂, …, a_N. O secvenţă nevidă în acest şir este de forma a_i, a_i+1, …, a_j, unde i ≤ j. De exemplu, pentru N=4 şi şirul 2 3 4 3, secvenţele nevide sunt: 2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3, 3. Definim puterea unui element a_i ca fiind numărul de secvenţe care-l conţin pe a_i şi în care a_i este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul 2 3 4 3 puterea elementului a₁ este 1 (fiind maxim doar în secvenţa formată din el însuşi), a elementului a₂ este 2 (a₂ fiind maxim în secvenţele 2 3 şi 3), a elementului a₃ este 6 (fiind maxim în secvenţele 2 3 4, 2 3 4 3, 3 4, 3 4 3, 4 şi 4 3), iar a elementului a₄ este 1.

Cerinţe

Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.

Date de intrare

Fișierul de intrare maxp.in conține pe prima linie numărul natural N, iar pe a doua linie, în ordine, numerele naturale a₁, a₂, …, a_N separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire maxp.out va conține pe prima linie un număr natural ce reprezintă puterea cea mai mare a unui element din şirul dat şi pe a doua linie va conţine un număr natural ce reprezintă numărul de elemente din şir care au cea mai mare putere.

Restricții și precizări

2 <= N <= 200.000
Elementele şirului sunt numere naturale şi au cel mult 6 cifre

Exemplul 1

maxp.in

7
9 3 4 5 1 2 2

maxp.out

12 
1

Explicație

Elementul 5 de pe poziţia 4 este maxim în 12 secvenţe:

3 4 5, 3 4 5 1, 3 4 5 1 2, 3 4 5 1 2 2, 4 5,

4 5 1, 4 5 1 2, 4 5 1 2 2, 5, 5 1, 5 1 2,

5 1 2 2, deci puterea lui este 12. Este singurul element care are această putere, celelalte elemente având puteri mai mici.

Exemplul 2

maxp.in

6
1 0 7 7 2 6

maxp.out

3 
2

Explicație

Elementele din poziţiile 3 şi 4 sunt maxime în 3 secvenţe, deci puterea lor este 3. Celelalte elemente au puteri mai mici.

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python2"> import sys

inFile = "maxp.intxt" outFile = "maxp.outtxt" dim = 200001

a = [0] * dim st = [0] * dim dr = [0] * dim q = [0] * dim poz = [0] * dim n = 0

def main():

   global n
   i, k, x, nrsol, p, pmax = 0, 0, 0, 0, 0, 0
   
   #citire
   with open(inFile, 'r') as fin:
       n = int(fin.readline())
       for i in range(1, n+1):
           a[i] = int(fin.readline())
   
   # constructie st
   k = 0
   q[k] = dim + 2
   poz[k] = 0
   st[k] = 0
   for i in range(1, n+1):
       x = a[i]
       while q[k] < x:
           k -= 1
       st[i] = i - poz[k] - 1
       k += 1
       q[k] = x
       poz[k] = i
   
   # constructie dr
   k = 0
   q[k] = dim + 2
   poz[k] = n + 1
   dr[k] = 0
   for i in range(n, 0, -1):
       x = a[i]
       while q[k] < x:
           k -= 1
       dr[i] = poz[k] - i - 1
       k += 1
       q[k] = x
       poz[k] = i

   # calcul
   nrsol = 1
   pmax = (st[1] + 1)
   pmax *= (dr[1] + 1)
   for i in range(2, n+1):
       p = (st[i] + 1)
       p = (p * (dr[i] + 1))
       if p > pmax:
           pmax = p
           nrsol = 1
       elif p == pmax:
           nrsol += 1
   
   with open(outFile, 'w') as fout:
       fout.write(str(pmax) + "\n" + str(nrsol) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>