oj.uz

Submission #719578

# Submission time Handle Problem Language Result Execution time Memory
719578 2023-04-06T10:04:28 Z keisuke6 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 742 ms 18044 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 346 ms 3932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 208 ms 14324 KB Output is correct
6 Correct 359 ms 14980 KB Output is correct
7 Correct 530 ms 15752 KB Output is correct
8 Correct 741 ms 18044 KB Output is correct
9 Correct 447 ms 3932 KB Output is correct
10 Correct 483 ms 4236 KB Output is correct
11 Correct 485 ms 4520 KB Output is correct
12 Correct 742 ms 16728 KB Output is correct
13 Correct 725 ms 18040 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -