Submission #599703

#	Time	Username	Problem	Language	Result	Execution time	Memory
599703		MilosMilutinovic	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2335 ms	430548 KiB

street_lamps

/**
 *    author:  wxhtzdy
 *    created: 19.07.2022 20:06:36
**/
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 3e5 + 5;
const int M = 120 * N; 

int root[N], ls[M], rs[M], tsz;
long long st[M];

void modify(int& c, int l, int r, int ll, int rr, int v) {
  if (!c) {
    c = ++tsz;
  }
  if (l > r || ll > rr || l > rr || r < ll) {
    return;
  }
  if (ll <= l && r <= rr) {
    st[c] += v;
    return;
  }
  int mid = l + r >> 1;
  modify(ls[c], l, mid, ll, rr, v);
  modify(rs[c], mid + 1, r, ll, rr, v);      
}

void modify(int x, int l, int r, int v) {
  for (x++; x < N; x += x & -x) {
    modify(root[x], 0, N - 1, l, r, v);
  }
}

void modify(int l, int r, int ll, int rr, int v) {
  modify(l, ll, rr, v);
  modify(r + 1, ll, rr, -v);
}

long long get(int c, int l, int r, int i) {
  if (!c) {
    return 0;
  }
  if (l == r) {
    return st[c];
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    return st[c] + get(ls[c], l, mid, i);
  } else {
    return st[c] + get(rs[c], mid + 1, r, i);
  }
}

int get(int x, int y) {
  long long res = 0;
  for (x++; x > 0; x -= x & -x) {
    res += get(root[x], 0, N - 1, y);
  }
  return res;
}  

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<pair<int, int>> segs;
  vector<bool> on(N);
  auto Add = [&](int i, int t) {
    pair<int, int> new_seg = {i, i}; 
    {
      auto it = segs.lower_bound({i + 1, -1});
      if (it != segs.begin()) {
        --it;
        auto p = *it;
        if (p.second == i - 1) {
          segs.erase(it);
          new_seg.first = p.first;
        }
      }
    }
    {
      auto it = segs.lower_bound({i + 1, -1});
      if (it != segs.end()) {
        auto p = *it;
        if (p.first == i + 1) {
          segs.erase(it);
          new_seg.second = p.second;
        }
      }
    }
    modify(new_seg.first, i, i, new_seg.second, -t);
    segs.emplace(new_seg);
    on[i] = true;
  };
  auto Remove = [&](int i, int t) {
    auto it = prev(segs.lower_bound({i + 1, -1}));
    auto p = *it;
    modify(p.first, i, i, p.second, +t);
    segs.erase(it);
    if (p.first < i) {
      segs.emplace(p.first, i - 1);
    }
    if (i < p.second) {
      segs.emplace(i + 1, p.second);
    }
    on[i] = false;
  };      
  for (int i = 0; i < n; i++) {
    if (s[i] == '1') {
      Add(i, 0);
    }
  } 
  for (int t = 1; t <= q; t++) {
    string op;
    cin >> op;
    if (op == "toggle") {
      int i;
      cin >> i;
      --i;     
      if (!on[i]) {
        Add(i, t);
      } else {
        Remove(i, t);
      }
    } else {
      int l, r;
      cin >> l >> r;
      --l; --r;
      int ans = get(l, r - 1);
      auto it = segs.lower_bound({l + 1, -1});
      if (it != segs.begin()) {
        --it;
        if (it->first <= l && it->second >= r - 1) {
          ans += t;
        }
      } 
      cout << ans << '\n';
    }
  }
  return 0;
}        

Compilation message (stderr)

street_lamps.cpp: In function 'void modify(int&, int, int, int, int, int)':
street_lamps.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'long long int get(int, int, int, int)':
street_lamps.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid = l + r >> 1;
      |             ~~^~~

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