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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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.