oj.uz

Submission #1046262

# Submission time Handle Problem Language Result Execution time Memory
1046262 2024-08-06T12:17:03 Z anastasiskolio Deda (COCI17_deda) C++14
140 / 140
 86 ms 7092 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 200000
#define INFTY 1000000000
int N, Q, T[4 * MAXN + 1];

void Build(int lo, int hi, int v) {
  if (lo == hi) {
    T[v] = INFTY;
    return;
  }
  int mid = (lo + hi) / 2;
  Build(lo, mid, 2 * v);
  Build(mid + 1, hi, 2 * v + 1);
  T[v] = min(T[2 * v], T[2 * v + 1]);
}

void Update(int lo, int hi, int v, int A, int X) {
  if (lo == hi) {
    T[v] = X;
    return;
  }
  int mid = (lo + hi) / 2;
  if (A <= mid)
    Update(lo, mid, 2 * v, A, X);
  else 
    Update(mid + 1, hi, 2 * v + 1, A, X);
  T[v] = min(T[2 * v], T[2 * v + 1]);
}

int Query(int lo, int hi, int v, int Y, int B) {
  if (lo == hi) 
    return T[v] <= Y && lo >= B ? lo : -1;
  int mid = (lo + hi) / 2;
  if (T[2 * v] <= Y && mid >= B) {
    int Q = Query(lo, mid, 2 * v, Y, B);
    if (Q != -1)
      return Q;
  }
  return Query(mid + 1, hi, 2 * v + 1, Y, B);
}

int main() {
  scanf("%d %d", &N, &Q);
  Build(1, N, 1);
  while (Q--) {
    char C;
    int A, B;
    scanf(" %c %d %d", &C, &A, &B);
    if (C == 'M')
      Update(1, N, 1, B, A);
    else 
      printf("%d\n", Query(1, N, 1, A, B));
  }
  return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d %d", &N, &Q);
      |   ~~~~~^~~~~~~~~~~~~~~~~
deda.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf(" %c %d %d", &C, &A, &B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 48 ms 6972 KB Output is correct
5 Correct 60 ms 6620 KB Output is correct
6 Correct 86 ms 6868 KB Output is correct
7 Correct 57 ms 7092 KB Output is correct