Submission #1302252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302252		tuncay_pasha	Deda (COCI17_deda)	C++20	0 / 140	549 ms	4724 KiB

deda

#include "bits/stdc++.h"

using namespace std;

#ifdef debug
  #include "debug.hpp"
#else
  #define dbg(...)
  #define dbgx(x)
  #define line()
#endif

#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define size(x) (int)(x.size())

const int N = 2e5 + 5;

int a[N];

struct SegTree {
  vi st;

  SegTree(int n) {
    st.assign(n * 4 + 5, 1e9);
  }

  void update(int v, int tl, int tr, int i, int x) {
    if (tl == tr) {
      st[v] = a[tl];
      return;
    }
    int tm = (tl + tr) >> 1;
    if (i <= tm) {
      update(v * 2, tl, tm, i, x);
    }
    else {
      update(v * 2 + 1, tm + 1, tr, i, x);
    }
    st[v] = min(st[v * 2], st[v * 2 + 1]);
  }

  int getRange(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return 1e9;
    if (l <= tl && tr <= r) return st[v];
    int tm = (tl + tr) >> 1;
    return min(getRange(v * 2, tl, tm, l, r), getRange(v * 2 + 1, tm + 1, tr, l, r));
  }
};

void _() {
  int n, q;
  cin >> n >> q;
  SegTree st(n);
  while (q--) {
    char c;
    cin >> c;
    if (c == 'M') {
      int i, x;
      cin >> x >> i;
      st.update(1, 1, n, i, x);
    }
    else {
      int i, x;
      cin >> x >> i;
      int lo = i, hi = n, best = -1;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (st.getRange(1, 1, n, i, mid) <= x) {
          best = mid;
          hi = mid - 1;
        }
        else lo = mid + 1;
      }
      cout << best << '\n';
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // freopen("in.txt", "r", stdin);
  int t = 1;
  // cin >> t;
  for (int cs = 1; cs <= t; ++cs) {
    _();
  }
  return 0;
}

• Subtask 1: 0 / 140