Submission #712302

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
712302	2023-03-18T14:33:07 Z	kdowwods	Deda (COCI17_deda)	C++17	140 / 140	113 ms	14164 KB

deda

#include <bits/stdc++.h>

#define INF 1000000100

using namespace std;

struct Node {
  int l, r;
  int minimum;
};

class ST {
 public:
  vector<Node> node;

  ST(int n) {
    node.resize(n * 4 + 4);
    init(1, n, 1);
  }

  void init(int l, int r, int id) {
    auto &nd = node[id];
    nd.l = l;
    nd.r = r;

    if (l < r) {
      int lid = leftId(id);
      int rid = rightId(id);
      int m = (l + r) / 2;

      init(l, m, lid);
      init(m + 1, r, rid);

      nd.minimum = min(node[lid].minimum, node[rid].minimum);
    } else {
      nd.minimum = INF;
    }
  }

  void set(int i, int a, int id = 1) {
    auto &nd = node[id];

    if (nd.l < nd.r) {
      int lid = leftId(id);
      int rid = rightId(id);

      set(i, a, i <= node[lid].r ? lid : rid);

      nd.minimum = min(node[lid].minimum, node[rid].minimum);
    } else {
      nd.minimum = a;
    }
  }

  int leftId(int id) { return id * 2; }
  int rightId(int id) { return id * 2 + 1; }

  int find(int i, int y, int id = 1) {
    auto &nd = node[id];

    if (nd.r < i || nd.minimum > y) {
      return INF;
    } else if (i <= nd.l && nd.l == nd.r) {
      return nd.l;
    } else {
      int lid = leftId(id);
      int rid = rightId(id);

      auto res = find(i, y, lid);
      if (res == INF) {
        res = find(i, y, rid);
      }
      return res;
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m;
  cin >> n >> m;

  ST st(n);

  char type;
  while (m--) {
    cin >> type;
    if (type == 'M') {
      int a, i;
      cin >> a >> i;
      st.set(i, a);
    } else {
      int y, i;
      cin >> y >> i;
      auto res = st.find(i, y);
      if (res == INF) {
        res = -1;
      }
      cout << res << "\n";
    }
  }
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	83 ms	14164 KB	Output is correct
5	Correct	89 ms	9004 KB	Output is correct
6	Correct	111 ms	11592 KB	Output is correct
7	Correct	113 ms	14156 KB	Output is correct