fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct tree {
  5.     long * tr;
  6.     tree(int n) {
  7.         tr = new long[4 * n + 1];
  8.     }
  9.     void build(int * arr, int v, int l, int r) {
  10.         if (l == r) tr[v] = arr[l];
  11.         else {
  12.             int mid = (l + r) / 2;
  13.             build(arr, v * 2, l, mid);
  14.             build(arr, v * 2 + 1, mid + 1, r);
  15.             tr[v] = tr[v * 2] + tr[v * 2 + 1];
  16.         }
  17.     }
  18.     void update(int v, int l, int r, int pos, int val) {
  19.         if (l == r) tr[v] = val;
  20.         else {
  21.             int mid = (l + r) / 2;
  22.             if (pos <= mid) update(v * 2, l, mid, pos, val);
  23.             else update(v * 2 + 1, mid + 1, r, pos, val);
  24.             tr[v] = tr[v * 2] + tr[v * 2 + 1];
  25.         }
  26.     }
  27.     int find(int v, int l, int r, int max) {
  28.         if (l == r)
  29.             return (tr[v] <= max);
  30.         int mid = (l + r) / 2;
  31.         if (tr[v * 2] > max)
  32.             return find(v * 2, l, mid, max);
  33.         else
  34.             return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);
  35.     }
  36. };
  37.  
  38. int main() {
  39.     int n, m, * arr;
  40.     cin >> n;
  41.     arr = new int[n + 1];
  42.     for (int i = 1; i <= n; ++i) cin >> arr[i];
  43.     tree tr(n);
  44.     tr.build(arr, 1, 1, n);
  45.     cin >> m;
  46.     int com, x, y, v;
  47.     for (int i = 0; i < m; ++i) {
  48.         cin >> com;
  49.         switch (com) {
  50.         case 1:
  51.             {
  52.                 cin >> v;
  53.                 cout << tr.find(1, 1, n, v) << '\n';
  54.                 break;
  55.             }
  56.         case 2:
  57.             {
  58.                 cin >> x >> y;
  59.                 tr.update(1, 1, n, x, y);
  60.                 break;
  61.             }
  62.         }
  63.     }
  64.     return 0;
  65. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
5
1 3 4 5 6
5
1 7
1 9
2 3 5
1 7
2 3 1
stdout
copy 
2
3
2
https://ideone.com/8yXXyG
language:
C++ 4.3.2 (gcc-4.3.2)
created:
4 years ago
visibility:
secret

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!