fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1e5 + 5; 
  5. int tree[4 * MAXN];
  6.  
  7. void build(int node, int start, int end) {
  8.     if (start == end) {
  9.         tree[node] = 0;
  10.     } else {
  11.         int mid = (start + end) / 2;
  12.         build(node*2, start, mid);
  13.         build(node*2+1, mid+1, end);
  14.         tree[node] = max(tree[node*2], tree[node*2+1]);
  15.     }
  16. }
  17. void update(int node, int start, int end, int i, int k) {
  18.     if (start == end) {
  19.         tree[node] = k;
  20.     } else {
  21.         int mid = (start + end) / 2;
  22.         if (i <= mid) {
  23.             update(node*2, start, mid, i, k);
  24.         } else {
  25.             update(node*2+1, mid+1, end, i, k);
  26.         }
  27.         tree[node] = max(tree[node*2], tree[node*2+1]);
  28.     }
  29. }
  30. int query(int node, int start, int end, int i, int j) {
  31.     if (i > end || j < start) {
  32.         return 0;
  33.     }
  34.     if (i <= start && end <= j) {
  35.         return tree[node]; 
  36.     }
  37.     int mid = (start + end) / 2;
  38.     int p1 = query(node*2, start, mid, i, j);
  39.     int p2 = query(node*2+1, mid+1, end, i, j);
  40.     return max(p1, p2); 
  41. }
  42.  
  43. int main() {
  44. //     freopen("QUERY.INP", "r", stdin);
  45. //     freopen("QUERY.OUT", "w", stdout);
  46.  
  47.     int n, m;
  48.     cin >> n >> m;
  49.  
  50.     build(1, 1, n); 
  51.  
  52.     for (int i = 0; i < m; i++) {
  53.         char type;
  54.         int a, b;
  55.         cin >> type >> a >> b;
  56.         if (type == 'S') {
  57.             update(1, 1, n, a, b);
  58.         } else if (type == 'Q') {
  59.             cout << query(1, 1, n, a, b) << "\n"; 
  60.         }
  61.     }
  62.  
  63.     return 0;
  64. }
  65.  
Runtime error #stdin #stdout 1.75s 2096020KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rGhJW9
language:
C++14 (gcc 8.3)
created:
233 days 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!