Editing 1057 - Max P

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

= 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 <code>maxp.in</code> conține pe prima linie numărul natural <code>N</code>, iar pe a doua linie, în ordine, numerele naturale <code>a<sub>1</sub></code>, <code>a<sub>2</sub></code>, …, <code>a<sub>N</sub></code> separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>maxp.out</code> 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 =

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

= Exemplul 1 =
<code>maxp.in</code>
 7
 9 3 4 5 1 2 2
<code>maxp.out</code>
 12 
 1

= Explicație =
Elementul <code>5</code> de pe poziţia <code>4</code> este maxim în <code>12</code> secvenţe: 

<code>3 4 5</code>, <code>3 4 5 1</code>, <code>3 4 5 1 2</code>, <code>3 4 5 1 2 2</code>, <code>4 5</code>, 

<code>4 5 1</code>, <code>4 5 1 2</code>, <code>4 5 1 2 2</code>, <code>5</code>, <code>5 1</code>, <code>5 1 2</code>, 

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

= Exemplul 2 =
<code>maxp.in</code>
 6
 1 0 7 7 2 6
<code>maxp.out</code>
 3 
 2

= Explicație =
Elementele din poziţiile <code>3</code> şi <code>4</code> sunt maxime în <code>3</code> secvenţe, deci puterea lor este <code>3</code>. 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>