# PBinfo #3219 – colina – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune 1 × N, fiind apoi împărțit în parcele de dimensiune 1 x 1. Pe fiecare dintre cele N parcele de dimensiune 1 × 1 firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la 1 la N, altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziție, unde se atinge altitudinea maximă a acestui teren, iar pentru pozițiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Mai precis, dacă notăm în ordine cu h1, h2, …, hN altitudinile parcelelor, există un indice vf, 1 ≤ vf ≤ N, astfel încât h1 < h2 <... < hvf-1 < hvf > hvf+1 > ... > hN.
Clienții au înregistrat deja cereri de construcție pentru M case. Fiecare dintre aceste cereri specifică însă o restricție mai ciudată, și anume faptul că doresc ca parcela de construcție să se afle exact la altitudinea qj (1 ≤ j ≤ M).

Cerința
Scrieți un program care determină pentru fiecare cerere j (1 ≤ j ≤ M) dacă firma poate îndeplini restricția respectivă, mai exact dacă există măcar o parcelă i (1 ≤ i ≤ N) pentru care hi = qj.

Date de intrare
Fișierul de intrare colina.in conține pe prima linie două numere naturale N şi M ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc N numere naturale h1, h2, …, hN, reprezentând altitudinile parcelelor. Pe ultima linie se găsesc M numere naturale q1, q2, …, qM, reprezentând altitudinile din cererile clienților. Numerele aflate pe aceeași linie sunt separate prin spații.

Date de ieșire
Fișierul de ieșire colina.out va conține M linii. Pe linia j (1 ≤ j ≤ M) va fi scris mesajul NU, dacă nu este posibilă construirea unei case la altitudinea qj. În caz contrar, pe linia j va fi scris mesajul DA, urmat de un spațiu, apoi de indicii i pentru care hi = qj, separați de asemenea prin câte spațiu și scriși în ordine crescătoare.

Restricții și precizări

1 ≤ N, M ≤ 100.000
0 < hi, qj < 231 pentru orice 1 ≤ i ≤ N și 1 ≤ j ≤ M.
Valorile qj sunt distincte (nu s-au acceptat cereri identice).
Pentru teste în valoare de 20 puncte:  N × M ≤ 100.000
Pentru teste în valoare de 40 puncte:  hmax ≤ 100.000 unde hmax este altitudinea maximă a parcelelor.

Exemplu:
colina.in

6 5
1 5 9 7 2 1
5 6 1 9 4
colina.out

DA 2
NU
DA 1 6
DA 3
NU

## Cod sursă C++

```cpp
#include <stdio.h>
#define NMax 100005
int n, m;
int h[NMax], q;
// binary search on interval [low, high]
// if condition == 0 searches for the position where the sequence becomes decreasing
// if condition == 1 searches for 'value' on a increasing sequence
// if condition == 2 searches for 'value' in a decreasung sequence
// expects the preconditions and does not check them
int binarySearch(int low, int high, int condition, int value) {
	while (high - low > 1) {
		int mi = (low + high) / 2;
		if ((condition == 0 && h[mi] > h[mi + 1]) ||
			(condition == 1 && h[mi] > q) ||
			(condition == 2 && h[mi] < q)) {
				high = mi;
		} else {
			low = mi;
		}
	}
	if (condition) {
		if (h[low] == value) {
			return low;
		} else if (h[high] == value) {
			return high;
		}
		return -1;
	} else {
		if (h[low] > h[low + 1])
			return low;
		else
			return high;
	}
}
int main() {
	freopen("colina.in", "rt", stdin);
	freopen("colina.out", "wt", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &h[i]);
	}
	n++;
	// this would also work in O(N)
	int posI = binarySearch(0, n - 1, 0, 0);
	for (int i = 0; i < m; i++) {
		scanf("%d", &q);
		// sequence is increasing on [0, posI]
		// sequence is decreasing on [posI, N-1]
		int posSmall = binarySearch(0, posI, 1, q);
		int posBig = binarySearch(posI + 1, n - 1, 2, q);
		if (posSmall != -1 && posBig != -1) {
			printf("DA %d %d\n", posSmall + 1, posBig + 1);
		} else if (posSmall != -1) {
			printf("DA %d\n", posSmall + 1);
		} else if (posBig != -1) {
			printf("DA %d\n", posBig + 1);
		} else {
			printf("NU\n");
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3219)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3219/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3219/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)