fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int n, m;
  9.     cin >> n >> m;
  10.  
  11.     int n2 = 1;
  12.     while (n2 < n) {
  13.         n2 *= 2;
  14.     }
  15.  
  16.     vector<pair<int, int>> v(2 * n2);
  17.  
  18.     // Liście
  19.     for (int i = n2; i < 2 * n2; i++) {
  20.         v[i].first = 0;
  21.         v[i].second = -i;
  22.     }
  23.  
  24.     // Wczytanie wartości
  25.     for (int i = n2; i < n2 + n; i++) {
  26.         cin >> v[i].first;
  27.         v[i].second = -i;
  28.     }
  29.  
  30.     // Budowanie drzewa
  31.     for (int i = n2 - 1; i > 0; i--) {
  32.         v[i].first = max(v[2 * i].first, v[2 * i + 1].first);
  33.  
  34.         if (v[2 * i].first >= v[2 * i + 1].first) {
  35.             v[i].second = v[2 * i].second;
  36.         } else {
  37.             v[i].second = v[2 * i + 1].second;
  38.         }
  39.     }
  40.  
  41.     for (int i = 0; i < m; i++) {
  42.         string x;
  43.         cin >> x;
  44.  
  45.         if (x == "PIORUN") {
  46.             int a, b, c;
  47.             cin >> a >> b >> c;
  48.  
  49.             a = a + n2 - 1;
  50.             b = b + n2 - 1;
  51.  
  52.             int d = INT_MIN;
  53.             int e = INT_MIN;
  54.  
  55.             // Szukanie maksimum na przedziale [a,b]
  56.             while (a <= b) {
  57.                 if (a % 2 == 1) {
  58.                     if (v[a].first > d) {
  59.                         d = v[a].first;
  60.                         e = v[a].second;
  61.                     } else if (v[a].first == d) {
  62.                         e = max(e, v[a].second);
  63.                     }
  64.                     a++;
  65.                 }
  66.  
  67.                 if (b % 2 == 0) {
  68.                     if (v[b].first > d) {
  69.                         d = v[b].first;
  70.                         e = v[b].second;
  71.                     } else if (v[b].first == d) {
  72.                         e = max(e, v[b].second);
  73.                     }
  74.                     b--;
  75.                 }
  76.  
  77.                 a /= 2;
  78.                 b /= 2;
  79.             }
  80.  
  81.             // e przechowuje ujemny indeks liścia
  82.             int pos = -e;
  83.  
  84.             // Zmniejszenie wartości o c, ale nie poniżej 0
  85.             v[pos].first = max(v[pos].first - c, 0);
  86.  
  87.             // Odbudowanie drzewa
  88.             int p = pos / 2;
  89.  
  90.             while (p > 0) {
  91.                 v[p].first = max(v[2 * p].first, v[2 * p + 1].first);
  92.  
  93.                 if (v[2 * p].first >= v[2 * p + 1].first) {
  94.                     v[p].second = v[2 * p].second;
  95.                 } else {
  96.                     v[p].second = v[2 * p + 1].second;
  97.                 }
  98.  
  99.                 p /= 2;
  100.             }
  101.  
  102.             // Twój sposób wypisywania drzewa
  103.             int z = 2;
  104.  
  105.             for (int j = 1; j < 2 * n2; j++) {
  106.                 if (j >= z) {
  107.                     cout << '\n';
  108.                     z *= 2;
  109.                 }
  110.  
  111.                 cout << v[j].first << " ";
  112.             }
  113.  
  114.             cout << '\n';
  115.  
  116.             // Pozycja w tablicy wejściowej + nowa wartość
  117.             cout << pos - n2 + 1 << " " << v[pos].first << '\n';
  118.         }
  119.  
  120.         else if (x == "WZROST") {
  121.             int a, b;
  122.             cin >> a >> b;
  123.  
  124.             a = a + n2 - 1;
  125.  
  126.             // Zwiększenie wartości
  127.             v[a].first += b;
  128.  
  129.             // Odbudowanie drzewa
  130.             int p = a / 2;
  131.  
  132.             while (p > 0) {
  133.                 v[p].first = max(v[2 * p].first, v[2 * p + 1].first);
  134.  
  135.                 if (v[2 * p].first >= v[2 * p + 1].first) {
  136.                     v[p].second = v[2 * p].second;
  137.                 } else {
  138.                     v[p].second = v[2 * p + 1].second;
  139.                 }
  140.  
  141.                 p /= 2;
  142.             }
  143.  
  144.             // Twój sposób wypisywania drzewa
  145.             int z = 2;
  146.  
  147.             for (int j = 1; j < 2 * n2; j++) {
  148.                 if (j >= z) {
  149.                     cout << '\n';
  150.                     z *= 2;
  151.                 }
  152.  
  153.                 cout << v[j].first << " ";
  154.             }
  155.  
  156.             cout << '\n';
  157.             cout << v[a].first << '\n';
  158.         }
  159.     }
  160.  
  161.     return 0;
  162. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6 5
3 0 5 7 2 1
PIORUN 5 6 3
WZROST 6 7
PIORUN 2 2 5
WZROST 2 1
PIORUN 2 5 3
stdout
copy 
7 
7 1 
3 7 1 0 
3 0 5 7 0 1 0 0 
5 0
8 
7 8 
3 7 8 0 
3 0 5 7 0 8 0 0 
8
8 
7 8 
3 7 8 0 
3 0 5 7 0 8 0 0 
2 0
8 
7 8 
3 7 8 0 
3 1 5 7 0 8 0 0 
1
8 
5 8 
3 5 8 0 
3 1 5 4 0 8 0 0 
4 4
https://ideone.com/GccJhr
language:
C++ (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!