Arranha-Céus da Nlogonia
Recentemente, com o aumento drástico de níveis do ar, o prefeito da Nlogonia está preocupado com os $$n$$ arranha-céus da cidade. Esses imensos prédios estão todos em uma avenida beira-mar, e portanto correm sério perigo. A cada dia, o nível do mar cresce por exatamente um metro, e cada prédio tem $$A_i$$ metros de altura. Consideraremos um $$quarteirao$$ de arranha-céus como uma sequência contígua de arranha-céus adjacentes tal que todas as alturas desses arranha-céus sejam estritamente maiores que o nível do mar atual. O prefeito da Nlogonia quer saber, em $$q$$ dias diferentes, quantos quarteirões ainda existem na cidade.
Entrada:
A primeira linha de entrada contém um inteiro $$t$$, o número de casos de teste. Seguem então $$t$$ casos de teste
A primeira linha de cada caso de teste contém dois inteiros: $$n$$ e $$q$$.
A segunda linha de cada caso de teste descreve os arranha-céus, em ordem, ou seja o $$i$$-ésimo arranha céu é adjacente ao$$i-1$$ ésimo arranha-céu, se existir, e ao $$i+1$$-ésimo arranha-céu, se existir. Essa linha contém $$n$$ inteiros, onde o $$i$$-ésimo inteiro indica $$A_i$$.
A terceira linha de cada caso indica os dias que o prefeito quer saber quantos quarteirões ainda existem, tendo $$q$$ inteiros $$d_i$$, dados em ordem estritamente crescente.
Saída
A saída deve conter $$q$$ inteiros, para cada caso de teste, onde o $$i$$-ésimo inteiro deve conter o número de quarteirões no dia $$d_i$$.
Restriçoes:
- $$1 \leq t \leq 15$$
- $$1 \leq n, q, \leq 10^6$$
- $$1 \leq A_i \leq 10^9$$
- $$0 \leq d_i \leq 10^9$$
Exemplos:
| Entrada | Saida |
2 3 3 1 2 3 1 2 3 5 3 1 3 5 1 3 0 2 4 |
1 1 0 1 2 1 |
NOTA: use as seguintes funções para leitura e impressão em C++:
Leitura:
| void getint(int &x){ | |
| register int c = getchar_unlocked(); | |
| x = 0; | |
| for(;(c<48 || c>57);c = getchar_unlocked()); | |
| for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c – 48;} | |
| } |
Saída:
| inline void print(int n){ | |
| if (n == 0) | |
| { | |
| putchar_unlocked('0'); | |
| putchar_unlocked('\n'); | |
| } | |
| else if (n == -1) | |
| { | |
| putchar_unlocked('-'); | |
| putchar_unlocked('1'); | |
| putchar_unlocked('\n'); | |
| } | |
| else | |
| { | |
| char buf[11]; | |
| buf[10] = ' '; | |
| int i = 9; | |
| while (n) | |
| { | |
| buf[i–] = n % 10 + '0'; | |
| n /= 10; | |
| } | |
| while (buf[i] != ' ') | |
| putchar_unlocked(buf[++i]); | |
| } | |
| } |
Para submeter sua solução use esse link.
