#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
int tt = 1, n;
string s;
int k[1001][1001];
int last[300005], kol[300005], l[300005], r[300005];
string type[300005];
int mx[4 * 300005];
void up(int l, int r, int ind, int num, int v){
if(l > ind || r < ind) return;
if(l == r){
mx[v] = num;
return;
}
int mid = (l + r) / 2;
up(l, mid, ind, num, v * 2);
up(mid + 1, r, ind, num, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
int get_mx(int l, int r, int l1, int r1, int v){
if(l > r1 || l1 > r) return 0;
if(l >= l1 && r1 >= r) return mx[v];
int mid = (l + r) / 2;
return max(get_mx(l, mid, l1, r1, v * 2), get_mx(mid + 1, r, l1, r1, v * 2 + 1));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> tt;
cin >> s;
// if(n <= 100 && tt <= 100){
// while(tt--){
// string ss;
// cin >> ss;
// for(int i = 1; i <= n; i++){
// for(int j = i + 1; j <= n + 1; j++){
// if(s[j - 2] == '1') k[i][j]++;
// else break;
// }
// }
// if(ss[0] == 'q'){
// int a, b;
// cin >> a >> b;
// cout << k[a][b] << "\n";
// }
// else{
// int p;
// cin >> p;
// if(s[p - 1] == '0') s[p - 1] = '1';
// else s[p - 1] = '0';
// }
// }
// return 0;
// }
bool f = 0;
for(int i = 1; i <= tt; i++){
cin >> type[i] >> l[i];
if(type[i][0] == 'q') cin >> r[i];
if(type[i][0] == 'q' && r[i] - 1 != l[i]) f = 1;
}
// if(!f){
// for(int i = 1; i <= tt; i++){
// if(type[i][0] == 'q'){
// int num = kol[l[i]];
// if(s[l[i] - 1] == '1') num += (i - last[l[i]]);
// cout << num << "\n";
// }
// else{
// if(s[l[i] - 1] == '1'){
// kol[l[i]] += (i - last[l[i]]);
// last[l[i]] = i;
// s[l[i] - 1] = '0';
// }
// else{
// last[l[i]] = i;
// s[l[i] - 1] = '1';
// }
// }
// }
// return 0;
// }
for(int i = 0; i < n; i++){
if(s[i] == '0') up(1, n, i + 1, 1e9, 1);
}
for(int i = 1; i <= tt; i++){
if(type[i][0] == 'q'){
cout << max(0, i - get_mx(1, n, l[i], r[i] - 1, 1)) << "\n";
}
else{
up(1, n, i, l[i], 1);
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:84:10: warning: variable 'f' set but not used [-Wunused-but-set-variable]
84 | bool f = 0;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
55 ms |
13400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12632 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
