結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー ZOI-dayo
提出日時 2025-10-28 17:35:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,240 bytes
コンパイル時間 2,805 ms
コンパイル使用メモリ 278,296 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-28 17:36:00
合計ジャッジ時間 5,116 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

//@yukicoder 3277

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T>
using vec = vector<T>;
template <class T>
using vv = vec<vec<T>>;
template <class T>
using vvv = vv<vec<T>>;
template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for (ll i = 0; i < (r); i++)
#define reps(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep(i, l, r) for (ll i = (r)-1; i >= l; i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
template <typename T>
bool chmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}

#define T ll
#define e 0LL
#define op(a, b) ((a) + (b))

struct SegTree {
  int n = 1;
  vec<T> v;

  // 構築 O(N log N)
  SegTree(int N) {
    while (n < N) n *= 2;
    v.assign(n * 2, e);
  }

  // 一点更新 O(log N)
  // i : [0, n)
  void update(int i, T a) {
    i += n;
    v[i] = a;
    while (i > 1) {
      i /= 2;
      v[i] = op(v[i * 2], v[i * 2 + 1]);
    }
  }

  // 区間総積取得 O(log N)
  // l : [0, n), r : [1, n], l < r
  T query(int l, int r, int x = 1, int lx = 0, int rx = -1) {
    if (rx < 0) rx = n;
    if (rx <= l || r <= lx) return e;
    if (l <= lx && rx <= r) return v[x];
    int m = (lx + rx) / 2;
    T lv = query(l, r, x * 2, lx, m), rv = query(l, r, x * 2 + 1, m, rx);
    return op(lv, rv);
  }

  int max_right(auto f) {
    if (!f(e)) return 0;
    if (f(v[1])) return n;
    T s = e;
    int i = 1;
    while (i < n) {
      int l = i << 1;
      T t = op(s, v[l]);
      if (f(t)) s = t, i = l + 1;
      else i = l;
    }
    return i - n;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  if (!(cin >> n >> q)) return 0;
  SegTree seg(n);
  rep(i, n) {
    ll x;
    cin >> x;
    seg.update(i, x);
  }
  rep(_, q) {
    int t;
    cin >> t;
    if (t == 0) {
      int i;
      ll x;
      cin >> i >> x;
      seg.update(i, x);
    } else {
      ll x;
      cin >> x;
      auto r = seg.max_right([&](ll s) { return s <= x; });
      cout << r << '\n';
    }
  }
  return 0;
}
0