fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define pii pair<int, int>
  4. #define MA 10000001
  5.  
  6. using namespace std;
  7.  
  8. struct node{
  9.     int val;
  10.     pii left, right;
  11.  
  12.     node(){
  13.         val= 0;
  14.         left.first = left.second = MA;
  15.         right.first = right.second = -1;
  16.     }
  17.  
  18.     void merge(const node& n1, const node& n2, int l, int r){
  19.         val = max(n1.val, n2.val);
  20.         left = n1.left;
  21.         right = n2.right;
  22.  
  23.         int l1 = n1.right.first, l2 = n1.right.second, r1 = n2.left.first, r2 = n2.left.second;
  24.         if(l1 != -1 && r1 != MA){
  25.             int t1 = l1, t2 = r2;
  26.             val = max(val, t2 - t1 + 1);
  27.             if(t1 == l) left = mp(t1, t2);
  28.             if(t2 == r) right = mp(t1, t2);
  29.         }
  30.     }
  31. };
  32.  
  33. node seg[300001];
  34.  
  35. int val[100001] = {0}, n;
  36.  
  37. void build(int l, int r, int i){
  38.     if(l == r){
  39.         if(!val[l]) return;
  40.         seg[i].val = 1;
  41.         pii p = mp(l, r);
  42.         seg[i].left = seg[i].right = p;
  43.         return;
  44.     }
  45.     int mid = (l+r)/2;
  46.     build(l, mid, i*2+1);
  47.     build(mid+1, r, i*2+2);
  48.     seg[i].merge(seg[i*2+1], seg[i*2+2], l, r);
  49. }
  50.  
  51. void update(int l, int r, int i, int pos){
  52.     if(l == r){
  53.         seg[i].val = 1;
  54.         pii p = mp(l, r);
  55.         seg[i].left = seg[i].right = p;
  56.         return;
  57.     }
  58.     int mid = (l+r)/2;
  59.     if(mid >= pos) update(l, mid, i*2+1, pos);
  60.     else update(mid+1, r, i*2+2, pos);
  61.     seg[i].merge(seg[i*2+1], seg[i*2+2], l, r);
  62. }
  63.  
  64. void print(){
  65.     for(int j = 0; j < 9; j++)
  66.         cout << j << " --> " << seg[j].val << " (" << seg[j].left.first << " " <<  seg[j].left.second << ") , (" << seg[j].right.first << " " << seg[j].right.second << ") " << endl;
  67. }
  68.  
  69. int main(){
  70.     ios_base :: sync_with_stdio(0);
  71.     cin.tie(0);
  72.  
  73.     int q;
  74.     cin >> n >> q;
  75.     string s;
  76.     cin >> s;
  77.     for(int j = 0; j < n; j++)
  78.         if(s[j] == '0') val[j] = 0;
  79.         else val[j] = 1;
  80.  
  81.     build(0, n-1, 0);
  82.     while(q--){
  83.         int type;
  84.         cin >> type;
  85.         if(type == 1) cout << seg[0].val << endl;
  86.         else{
  87.             int x;
  88.             cin >> x;
  89.             x--;
  90.             if(val[x] == 1) continue;
  91.             update(0, n-1, 0, x);
  92.             val[x] = 1;
  93.             //print();
  94.         }
  95.     }
  96.     return 0;
  97. }
Success #stdin #stdout 0s 8840KB
comments (?)
stdin
copy 
5 7
00000
1
2 3
1
2 5
1
2 4
1
stdout
copy 
0
1
1
3
https://ideone.com/v9fg9A
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!