Submission #974108

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
974108	2024-05-02T19:45:08 Z	anastasiskolio	Deda (COCI17_deda)	C++14	0 / 140	1000 ms	3312 KB

deda

#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 Query(int lo, int hi, int v, int y, int b) {
  if (lo == hi) {
    return tree[v] <= y ? lo : -1;
  }
  int mid = (lo + hi)/2;
  if (tree[2*v] <= y && mid >= b) {
    int q1 = Query(lo, mid, 2*v, y, b);
    if (q1 == -1)
      return Query(mid + 1, hi, 2*v + 1, y, b);
  }
  else { 
    return Query(mid + 1, hi, 2*v + 1, y, b);
  }
}

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 
       printf("%d\n", Query(1, n, 1, a, b));
      //Query(b, n, a);
  }
  return 0;
}

Compilation message

deda.cpp: In function 'int Query(int, int, int, int, int)':
deda.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^
deda.cpp: In function 'int main()':
deda.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
deda.cpp:73:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     char task; int a, b; scanf(" %c%d%d", &task, &a, &b);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Output isn't correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Incorrect	5 ms	344 KB	Output isn't correct
4	Incorrect	356 ms	3312 KB	Output isn't correct
5	Execution timed out	1034 ms	2920 KB	Time limit exceeded
6	Execution timed out	1043 ms	2912 KB	Time limit exceeded
7	Execution timed out	1063 ms	2972 KB	Time limit exceeded