답안 #490310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490310	2021-11-26T23:26:17 Z	lto5	Deda (COCI17_deda)	C++14	140 / 140	115 ms	6864 KB

deda

#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

#	결과	실행 시간	메모리	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