답안 #974141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974141 2024-05-02T22:27:18 Z anastasiskolio Deda (COCI17_deda) C++14
100 / 140
719 ms 5816 KB
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define INFTY 1e9 + 1
int n, q, tree[4 * MAXN + 1];
 
void Build(int lo, int hi, int v) {
  if (lo == hi) {
    tree[v] = INFTY;
    return;
  }
  int mid = (lo + hi) / 2;
  Build(lo, mid, 2 * v);
  Build(mid + 1, hi, 2 * v + 1);
  tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
 
void Update(int lo, int hi, int v, int i, int delta) {
  if (lo == hi) {
    tree[v] = delta;
    return;
  }
  int mid = (lo + hi) / 2;
  if (i <= mid)
    Update(lo, mid, 2 * v, i, delta);
  else 
    Update(mid + 1, hi, 2 * v + 1, i, delta);
  tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
 
int Min(int lo, int hi, int v, int l, int r) {
    if (l <= lo && hi <= r)
      return tree[v];
    if (l > hi || r < lo)
      return INFTY;
    int mid = (lo + hi) / 2;
    int MinL = Min(lo, mid, 2 * v, l, r);
    int MinR = Min(mid + 1, hi, 2 * v + 1, l, r);
    return min(MinL, MinR);
}
 
void Query(int lo, int hi, int y) {
  if (lo == hi) {
    printf("%d\n", Min(1, n, 1, lo, lo) <= y ? lo : -1);
    return;
  }
  int j = (lo + hi) / 2;
  if (Min(1, n, 1, lo, j) <= y)
    Query(lo, j, y);
  else 
    Query(j + 1, hi, y);
}
 
int main() {
  scanf("%d %d", &n, &q);
  Build(1, n, 1);
  while (q--) {
    char task; int a, b; scanf(" %c %d %d", &task, &a, &b);
    if (task == 'M')
      Update(1, n, 1, b, --a);
    else 
      Query(b, n, a);
  }
  return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d %d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~
deda.cpp:58:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     char task; int a, b; scanf(" %c %d %d", &task, &a, &b);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 6 ms 344 KB Output isn't correct
4 Correct 719 ms 5756 KB Output is correct
5 Correct 454 ms 5212 KB Output is correct
6 Correct 556 ms 5816 KB Output is correct
7 Correct 601 ms 5716 KB Output is correct