Submission #1046266

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046266	2024-08-06T12:18:07 Z	anastasiskolio	Deda (COCI17_deda)	C++14	140 / 140	55 ms	3676 KB

deda

#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	348 KB	Output is correct
4	Correct	45 ms	3676 KB	Output is correct
5	Correct	52 ms	3412 KB	Output is correct
6	Correct	54 ms	3408 KB	Output is correct
7	Correct	55 ms	3408 KB	Output is correct