2733 - nrapp

Cerința

Se dă un număr natural N si un șir v de N numere naturale. Sa se răspundă la Q întrebări de tipul:

D y: Care este cea mai mică poziție x, unde x > y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi N + 1. S y: Care este cea mai mare poziție x, unde x < y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi 0.

Date de intrare

Fișierul de intrare nrapp.in conține pe prima linie numărul natural N, iar pe a doua linie N numere naturale separate prin spații. A treia linie va conține numărul natural nenul Q și apoi Q întrebări precum cele descrise anterior.

Date de ieșire

Fișierul de ieșire nrapp.out va conține Q linii, anume răspunsul pentru fiecare întrebare în parte.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ v[i] ≤ 1.000.000

Exemplu:

nrapp.in

8

1 3 6 5 2 1 9 6

8

S 1

D 2

D 3

S 4

S 5

D 6

D 7

D 8

nrapp.out

0

5

4

2

1

9

8

9

Rezolvare

# Functia solve care rezolva problema
def solve(N, v, Q, queries):
    # Initializam lista de raspunsuri
    answers = []
    # Parcurgem fiecare interogare
    for query in queries:
        # Daca interogarea este de tip 'D'
        if query[0] == 'D':
            y = query[1]
            # Initializam raspunsul cu N + 1
            answer = N + 1
            # Cautam cea mai mica pozitie x > y pentru care v[x] < v[y]
            for x in range(y + 1, N + 1):
                if v[x - 1] < v[y - 1]:
                    answer = x
                    break
            # Adaugam raspunsul in lista de raspunsuri
            answers.append(answer)
        # Daca interogarea este de tip 'S'
        elif query[0] == 'S':
            y = query[1]
            # Initializam raspunsul cu 0
            answer = 0
            # Cautam cea mai mare pozitie x < y pentru care v[x] < v[y]
            for x in range(y - 1, 0, -1):
                if v[x - 1] < v[y - 1]:
                    answer = x
                    break
            # Adaugam raspunsul in lista de raspunsuri
            answers.append(answer)
    # Returnam lista de raspunsuri
    return answers

# Citirea datelor de intrare din fisierul nrapp.in
with open('nrapp.in', 'r') as file:
    N = int(file.readline())
    v = list(map(int, file.readline().split()))
    Q = int(file.readline())
    queries = []
    for _ in range(Q):
        query = file.readline().split()
        queries.append((query[0], int(query[1])))

# Rezolvarea problemei
answers = solve(N, v, Q, queries)

# Scrierea raspunsurilor in fisierul nrapp.out
with open('nrapp.out', 'w') as file:
    for answer in answers:
        file.write(str(answer) + '\n')