oj.uz

Submission #490310

# Submission time Handle Problem Language Result Execution time Memory
490310 2021-11-26T23:26:17 Z lto5 Deda (COCI17_deda) C++14
140 / 140
 115 ms 6864 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 5;
const int INF = INT_MAX;

int st[MAX_N << 2];

void update(int id, int l, int r, int i, int val){
  if(i < l || r < i)
    return;
  if(l == r){
    st[id] = val;
    return;
  }
  int m = l + r >> 1;
  update(id << 1, l, m, i, val);
  update(id << 1 | 1, m + 1, r, i, val);
  st[id] = min(st[id << 1], st[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v){
  if(r < u || v < l)
    return INF;
  if(u <= l && r <= v)
    return st[id];
  int m = l + r >> 1;
  return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}

void build(int id, int l, int r){
  if(l == r){
    st[id] = INF;
    return;
  }
  int m = l + r >> 1;
  build(id << 1, l, m);
  build(id << 1 | 1, m + 1, r);
  st[id] = min(st[id << 1], st[id << 1 | 1]);
}

// walk on segment tree
int query(int id, int l, int r, int lowerbound, int k){
  if(st[id] > k)
    return -1;
  if(r < lowerbound)
    return -1;
  if(l == r)
    return l;
  int m = l + r >> 1;
  int res = -1;
  if(st[id << 1] <= k)
    res = query(id << 1, l, m, lowerbound, k);
  if(res == -1)
    res = query(id << 1 | 1, m + 1, r, lowerbound, k);
  return res;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n, q;
  cin >> n >> q;
  build(1, 1, n);

  while(q--){
    char type;
    cin >> type;

    if(type == 'M'){
      int x, a;
      cin >> x >> a;
      update(1, 1, n, a, x);
    }
    
    else{
      int y, b;
      cin >> y >> b;
      cout << query(1, 1, n, b, y) << '\n';
    }
  }

  return 0;
}

Compilation message

deda.cpp: In function 'void update(int, int, int, int, int)':
deda.cpp:16:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   int m = l + r >> 1;
      |           ~~^~~
deda.cpp: In function 'int get(int, int, int, int, int)':
deda.cpp:27:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int m = l + r >> 1;
      |           ~~^~~
deda.cpp: In function 'void build(int, int, int)':
deda.cpp:36:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int m = l + r >> 1;
      |           ~~^~~
deda.cpp: In function 'int query(int, int, int, int, int)':
deda.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m = l + r >> 1;
      |           ~~^~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 76 ms 6864 KB Output is correct
5 Correct 83 ms 5364 KB Output is correct
6 Correct 115 ms 6616 KB Output is correct
7 Correct 87 ms 6748 KB Output is correct