제출 #719578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719578		keisuke6	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	742 ms	18044 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define int long long
template <typename T>
struct RMQ {
    const T INF = 0;
    int n;         // 葉の数
    vector<T> dat; // 完全二分木の配列
    RMQ(int n_) : n(), dat(n_ * 4, INF) { // 葉の数は 2^x の形
        int x = 1;
        while (n_ > x) {
            x *= 2;
        }
        n = x;
    }
    void update(int i, T x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;  // parent
            dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return INF;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return max(vl, vr);
        }
    }
};
signed main(){
  int N,Q;
  string S;
  cin>>N>>Q>>S;
  RMQ<int> seg(N);
  for(int i=0;i<N;i++){
    if(S[i] == '1') seg.update(i,0);
    else seg.update(i,1e18);
  }
  for(int i=0;i<Q;i++){
    string s;
    cin>>s;
    if(s[0] != 'q'){
      int a;
      cin>>a;
      seg.update(a-1,i+1);
      continue;
    }
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    cout<<(seg.query(a,b) == 1e18 ? 0 : i+1-seg.query(a,b))<<endl;
  }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20