fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4.  
  5. set<pii> init(string s) {
  6.     s += '0';
  7.     int prev = 0;
  8.     set<pii> ret;
  9.  
  10.     // 1 が連続する区間を全て set に入れる
  11.     for(size_t i=0; i<s.length(); i++) {
  12.         if(s[i-1] == '1' && s[i] == '0') ret.insert(pii(prev, i-1));
  13.         if(s[i-1] == '0' && s[i] == '1') prev = i;
  14.     }
  15.     return ret;
  16. }
  17.  
  18. int main() {
  19.     int n, q; cin >> n;
  20.     string s; cin >> s;
  21.  
  22.     set<pii> range = init(s);
  23.     range.insert(pii(-1e9, -1e9));
  24.     range.insert(pii( 1e9,  1e9));
  25.     cin >> q;
  26.     for(int i=0; i<q; i++) {
  27.         int l, r, b; cin >> l >> r >> b;
  28.         l--; r--;
  29.  
  30.         // 左端が l を超えない最大の値である区間を取る
  31.         auto it = range.upper_bound(pii(l,0)); it--;
  32.         int x = (*it).first, y = (*it).second;
  33.  
  34.         // 既存の区間がクエリの区間を被覆している
  35.         if(x <= l && r <= y) {
  36.             if(b == 0) {
  37.                 range.erase(it);
  38.                 if(x <= l-1) range.insert(pii(x, l-1));
  39.                 if(r+1 <= y) range.insert(pii(r+1, y));
  40.             }
  41.         }
  42.         // 既存の区間がクエリの区間を被覆しない (4 つの可能性がある)
  43.         // -> クエリの区間が既存の区間を被覆している
  44.         // -> クエリの区間が既存の区間の左一部を被覆している
  45.         // -> クエリの区間が既存の区間の右一部を被覆している
  46.         // -> 既存のクエリとクエリの区間が接している (1 に更新するときに気をつけなければならない)
  47.         else {
  48.             auto it2 = range.lower_bound(pii(l,0)); it2--;
  49.             if(b == 0) {
  50.                 while((*it2).first <= r) {
  51.                     x = (*it2).first, y = (*it2).second;
  52.                     bool ok = false;
  53.                     // 右一部
  54.                     if(x <= l && l <= y) {
  55.                         if(x <= l-1) range.insert(pii(x, l-1));
  56.                         ok = true;
  57.                     }
  58.                     // 左一部
  59.                     if(x <= r && r <= y) {
  60.                         if(r+1 <= y) range.insert(pii(r+1, y));
  61.                         ok = true;
  62.                     }
  63.                     // 既存の区間を被覆
  64.                     if((l <= x && y <= r) || ok) {
  65.                         it2 = range.erase(it2);
  66.                     }
  67.                     else it2++;
  68.                 }
  69.             }
  70.             else {
  71.                 int L = l, R = r;
  72.                 while(1) {
  73.                     x = (*it2).first, y = (*it2).second;
  74.                     // どのパターンでもやることは変わらない
  75.                     bool b1 = (x <= L && L <= y);
  76.                     bool b2 = (x <= R && R <= y);
  77.                     bool b3 = (L <= x && y <= R);
  78.                     bool b4 = (L - 1 == y);
  79.                     bool b5 = (R + 1 == x);
  80.                     if(b1 || b2 || b3 || b4 || b5) {
  81.                         it2 = range.erase(it2);
  82.                         L = min(L, x);
  83.                         R = max(R, y);
  84.                     }
  85.                     else {
  86.                         if((*it2).first <= r) it2++;
  87.                         else break;
  88.                     }
  89.                 }
  90.                 range.insert(pii(L, R));
  91.             }
  92.         }
  93.         cout << range.size() - 2 << endl;
  94.     }
  95.     return 0;
  96. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
10
0101100110
3
3 3 1
1 6 0
2 5 1
stdout
copy 
2
1
2
https://ideone.com/O6vpLu
language:
C++ (gcc 8.3)
created:
7 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!