Submission #551161

#	Time	Username	Problem	Language	Result	Execution time	Memory
551161		Soumya1	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2441 ms	216980 KiB

street_lamps

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 3e5 + 2;
vector<int> t[4 * mxN], kk[mxN];
int sz[4 * mxN];
vector<tuple<int, int, int, int>> g;
struct BIT {
  vector<pair<int, int>> bit;
  int n;
  BIT() { }
  BIT(int _n) {
    n = _n;
    bit.assign(n + 1, {0, 0});
  }
  void add(int i, int a, int b) {
    for (; i <= n; i = i | (i + 1)) bit[i].first += a, bit[i].second += b;
  }
  pair<int, int> sum(int r) {
    pair<int, int> ret = {0, 0};
    for (; r >= 1; r = (r & (r + 1)) - 1) {
      ret.first += bit[r].first;
      ret.second += bit[r].second;
    }
    return ret;
  }
  pair<int, int> sum(int l, int r) {
    auto a = sum(r);
    auto b = sum(l - 1);
    return {a.first - b.first, a.second - b.second};
  }
} bb[4 * mxN];
void build(int x, int lx, int rx) {
  if (lx == rx) {
    t[x] = kk[lx];
    t[x].push_back(1e9);
    sort(t[x].begin(), t[x].end());
    t[x].erase(unique(t[x].begin(), t[x].end()), t[x].end());
    sz[x] = t[x].size();
    bb[x] = BIT(sz[x]);
    // cout << x << " " << lx << " " << rx << "    ";
    // for (int i : t[x]) cout << i << " "; cout << endl;
    return;
  }
  int mx = (lx + rx) >> 1;
  build(x << 1, lx, mx);
  build(x << 1 | 1, mx + 1, rx);
  merge(t[x << 1].begin(), t[x << 1].end(), t[x << 1 | 1].begin(), t[x << 1 | 1].end(), back_inserter(t[x]));
  t[x].erase(unique(t[x].begin(), t[x].end()), t[x].end());
  sz[x] = t[x].size();
  bb[x] = BIT(sz[x]);
// cout << x << " " << lx << " " << rx << "    ";
//     for (int i : t[x]) cout << i << " "; cout << endl;
}
void update(int x, int lx, int rx, int i, int y, int timer, int tt) {
  if (lx == rx) {
    // cout << lx << " " << rx << " " << y << " " << mp[x][y] << " " << timer << " " << tt << endl;
    int yy = lower_bound(t[x].begin(), t[x].end(), y) - t[x].begin() + 1;
    bb[x].add(yy, timer, tt);
    return;
  }
  int mx = (lx + rx) >> 1;
  if (i <= mx) update(x << 1, lx, mx, i, y, timer, tt);
  else update(x << 1 | 1, mx + 1, rx, i, y, timer, tt);
  int yy = lower_bound(t[x].begin(), t[x].end(), y) - t[x].begin() + 1;
  bb[x].add(yy, timer, tt);
      // cout << lx << " " << rx << " " << y << " " << mp[x][y] << " " << timer << " " << tt << endl;

}
pair<int, int> query(int x, int lx, int rx, int l, int r, int y) {
  if (lx > r || l > rx) return {0, 0};
  if (l <= lx && r >= rx) {
    int yy = lower_bound(t[x].begin(), t[x].end(), y) - t[x].begin();
    // cout << lx << " " << rx << " " << mp[x][t[x][yy]] << " ";
    return bb[x].sum(yy + 1, sz[x]);
  }
  int mx = (lx + rx) >> 1;
  auto a = query(x << 1, lx, mx, l, r, y);
  auto b = query(x << 1 | 1, mx + 1, rx, l, r, y);
  return {a.first + b.first, a.second + b.second};
}
void testCase() {
  int n, q;
  cin >> n >> q;
  {
    string s;
    cin >> s;
    s = '0' + s;
    s += '0';
    int l = -1;
    set<pair<int, int>> st;
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1' && s[i - 1] != '1') l = i;
      if (s[i] == '1' && s[i + 1] != '1') {
        g.push_back({0, 1, l, i + 1});
        st.insert({l, i + 1});
      }
    }
    for (int time = 1; time <= q; time++) {
      string t;
      cin >> t;
      if (t[0] == 'q') {
        int a, b;
        cin >> a >> b;
        g.push_back({time, 3, a, b});
      } else {
        int i;
        cin >> i;
        if (s[i] == '1') {
          auto p = *prev(st.upper_bound({i, 1e9}));
          st.erase(p);
          g.push_back({time, 2, p.first, p.second});
          if (s[i - 1] == '1') {
            g.push_back({time, 1, p.first, i});
            st.insert({p.first, i});
          }
          if (s[i + 1] == '1') {
            g.push_back({time, 1, i + 1, p.second});
            st.insert({i + 1, p.second});
          }
          s[i] = '0';
        } else {
          if (s[i + 1] == '1' && s[i - 1] == '1') {
            auto p = *st.upper_bound({i, 0});
            g.push_back({time, 2, p.first, p.second});
            st.erase(p);
            auto pp = *prev(st.upper_bound({i, 0}));
            st.erase(pp);
            g.push_back({time, 2, pp.first, pp.second});
            st.insert({pp.first, p.second});
            g.push_back({time, 1, pp.first, p.second});
          } else if (s[i + 1] == '1') {
            auto p = *st.upper_bound({i, 0});
            st.erase(p);
            g.push_back({time, 2, p.first, p.second});
            st.insert({i, p.second});
            g.push_back({time, 1, i, p.second});
          } else if (s[i - 1] == '1') {
            auto p = *prev(st.lower_bound({i, 0}));
            st.erase(p);
            g.push_back({time, 2, p.first, p.second});
            st.insert({p.first, i + 1});
            g.push_back({time, 1, p.first, i + 1});
          } else {
            g.push_back({time, 1, i, i + 1});
            st.insert({i, i + 1});
          }
          s[i] = '1';
        }
      }
    }
  }
  sort(g.begin(), g.end());
  for (auto [a, b, c, d] : g) {
    // cout << a << " " << b << " " << c << " " << d << endl;
    kk[c].push_back(d);
  }
  build(1, 1, n);
  for (auto [a, b, c, d] : g) {
    if (b == 1) {
      update(1, 1, n, c, d, -a, 1);
    } else if (b == 2) {
      update(1, 1, n, c, d, a, -1);
    } else {
      auto x = query(1, 1, n, 1, c, d);
      cout << 1LL * a * x.second + x.first << "\n";
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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