# PBinfo #3759 – Cartita – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: deivid ## Enunț În grădina lui Macarie există un șir de N morcovi, numerotați de la 1 la N. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălțimea de h[i] centimetri. O cârtiță neastâmpărată sapă galerii subterane pe sub morcovii lui Macarie. Când sapă o galerie către un morcov, tot pământul rezultat îl scoate afară modificând astfel înălțimea grămăjoarei corespunzătoare acelui morcov, dar și ale celorlalți morcovi din grădină. Dacă în urma săpării unei galerii către morcovul de pe poziția pos înălțimea grămăjoarei lui a crescut cu x centimetri, atunci înălțimile grămăjoarelor tuturor morcovilor se modifică după următoarea regulă ce depinde de un număr K: înălțimea grămăjoarei morcovului pos - 1 se modifică cu x - K centimetri iar a morcovului pos + 1 cu x + K centimetri, înălțimile gramăjoarelor morcovilor pos - 2 și pos + 2 se modifică cu x - 2 * K respectiv x + 2 * K centimetri În caz general, înălțimea se modifică după următoarele reguli pentru fiecare morcov din grădină: - Înălțimea h[pos - i] devine h[pos - i] + x - i * K, pentru fiecare i, 1 ≤ i ≤ pos-1 - Înălțimea h[pos + i] devine h[pos + i] + x + i * K, pentru fiecare i, 1 ≤ i ≤ N-pos Cerința Se cunosc înălțimile inițiale ale tuturor celor N grămăjoare și cele U modificări făcute de cârtiță asupra înălțimilor grămăjoarelor de pământ ale morcovilor. Știm că în cadrul unei secvențe continue de morcovi cel mai tentant pentru cârtiță este morcovul cu cea mai mică înălțime a grămăjoarei de pământ. Ajutați-l pe Macarie să identifice înălțimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiță. Date de intrare Fișierul de intrare cartita.in conţine pe prima linie un număr natural N având semnificația din enunț. Pe următoarea linie se află N numere naturale despărțite prin câte un spațiu, reprezentând în ordine, înălțimile grămăjoarelor de pământ, al i-lea număr reprezentând înălțimea inițială h[i], a grămăjoarei din dreptul morcovului i. Pe a treia linie se află un număr natural U reprezentând numărul de morcovi către care cărtița a săpat galerii. Pe următoarele U linii se află câte un triplet de numere naturale pos, x, K, separate între ele prin câte un spațiu, cu semnificația că în urma săpării unei galerii către morcovul pos înălțimea grămăjoarei lui a crescut cu x centimetri, iar celelalte înălțimi se modifică, după regula descrisă în enunț. Pe următoarea linie se găsește numărul Q reprezentând numărul de intervale unde se dorește identificarea înălțimii minime a unei grămăjoare corespunzătoare celui mai tentant morcov. Pe următoarele Q linii sunt câte două numere naturale L, R, separate între ele printr-un spațiu, reprezentând capetele intervalului de morcovi investigat. Date de ieșire Fişierul de ieşire cartita.out va conţine Q linii, pe fiecare găsindu-se, în ordine, răspunsul la intervalele investigate. Restricții și precizări 1 ≤ N ≤ 100.000 1 ≤ U ≤ 300.000 1 ≤ Q ≤ 200.000 1 ≤ L ≤ R ≤ N Inițial 1 ≤ h[i] ≤ N, pentru fiecare i, 1 ≤ i ≤ N 1 ≤ pos ≤ N, 1 ≤ x ≤ 400 și -21 ≤ K ≤ 21, K ≠ 0 Exemplu: cartita.in 6 1 6 2 4 3 4 3 4 5 2 2 4 1 4 2 8 3 1 6 2 4 4 4 cartita.out -19 -3 17 Explicație După prima galerie săpată către morcovul 4, șirul înălțimilor celor N=6 grămăjoare a devenit (0, 7, 5, 9, 10, 13). După a doua galerie săpată către morcovul 2, șirul înălțimilor celor N=6 grămăjoare a devenit (3, 11, 10, 15, 17, 21). După a treia galerie săpată către morcovul 4, șirul înălțimilor celor N=6 grămăjoare a devenit (-19, -3, 4, 17, 27, 39) Pe intervalul [1,6], înălțimea minimă este -19, pe intervalul [2,4], înălțimea minimă este -3, iar pentru ultimul interval investigat [4,4] înălțimea minimă este 17. ## Cod sursă C++ ```cpp ///O(U + N*log2N + Q) #include #include using namespace std; ifstream f("cartita.in"); ofstream g("cartita.out"); const int NMAX = 1e5 + 1, LOGMAX = 17; const long long INF = 1LL * 1e18; int N, U, Q; long long A[NMAX]; long long Sum_X = 0, Sum_K = 0; long long Diff = 0; int Log2[NMAX]; long long rmq[LOGMAX][NMAX]; void Read () { f >> N; assert(1 <= N && N <= 1e5); for(int i = 1; i <= N; ++i) f >> A[i], assert(1 <= A[i] && A[i] <= N); return; } void Update () { int i = 0, x = 0, K = 0; f >> i >> x >> K; assert(1 <= i && i <= N); assert(1 <= x && x <= 400); assert(-21 <= K && K <= 21 && K); /// assert(1 <= x && x <= 1e3); /// assert(1 <= K && K <= 21); Sum_X += 1LL * x, Sum_K += 1LL * K; Diff += 1LL * i * K; return; } long long my_min (long long a, long long b) { return ((a < b) ? a : b); } void Initialize () { Log2[1] = 0; for(int i = 1; i <= N; ++i) { if(i > 1) Log2[i] = 1 + Log2[(i >> 1)]; rmq[0][i] = A[i]; } for(int i = 1; i <= Log2[N]; ++i) { int Lg = (1 << i); for(int j = 1; j <= (N - Lg + 1); ++j) rmq[i][j] = my_min(rmq[i - 1][j], rmq[i - 1][j + (Lg >> 1)]); } return; } void Updates () { f >> U; assert(1 <= U && U <= 3e5); while(U--) Update(); for(int i = 1; i <= N; ++i) A[i] += 1LL * Sum_X + 1LL * i * Sum_K - Diff; Initialize(); return; } long long Query_Min (int left, int right) { int k = Log2[(right - left + 1)]; return my_min(rmq[k][left], rmq[k][right - (1 << k) + 1]); } void Query () { int left = 0, right = 0; f >> left >> right; assert(1 <= left && left <= right && right <= N); g << Query_Min(left, right) << '\n'; return; } void Queries () { f >> Q; assert(1 <= Q && Q <= 2e5); while(Q--) Query(); return; } int main() { Read(); Updates(); Queries(); return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3759) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3759/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3759/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)