Submission #189134

#	Time	Username	Problem	Language	Result	Execution time	Memory
189134		AlexPop28	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	2992 ms	172412 KiB

street_lamps

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

struct Fenwick {
  int n;
  vector<int> tree;
  Fenwick(int n_ = 0) : n(n_), tree(n + 1) {}
  inline int lsb(int x) {
    return x & -x;
  }
  void Update(int pos, int val) {
    for (++pos; pos <= n; pos += lsb(pos))
      tree[pos] += val;
  }
  void Update(int left, int right, int val) {
    Update(left, val);
    Update(right + 1, -val);
  }
  int Query(int pos) {
    int ans = 0;
    for (++pos; pos; pos -= lsb(pos))
      ans += tree[pos];
    return ans;
  }
};

struct SegmTree {
  int n;
  vector<Fenwick> tree;
  vector<vector<int>> qrs;
  SegmTree(int n_) : n(n_), tree(4 * n), qrs(4 * n) {}
  void Build() {
    for (int node = 0; node < 4 * n; ++node) {
      sort(qrs[node].begin(), qrs[node].end());
      qrs[node].erase(unique(qrs[node].begin(), qrs[node].end()), qrs[node].end());
      tree[node] = Fenwick(qrs[node].size());
    }
  }

  void AddQuery(int node, int left, int right, int a, int b) {
    qrs[node].emplace_back(b);
    if (left == right) return;
    int mid = left + (right - left) / 2;
    if (a <= mid) {
      AddQuery(2 * node + 1, left, mid, a, b);
    } else {
      AddQuery(2 * node + 2, mid + 1, right, a, b);
    }
  }

  void Update(int node, int left, int right, int x, int y, int val) {
    if (qrs[node].empty()) return;
    if (x <= left && right <= y) {
      // vreau queryurile care au capatul dreapta <= y
      // capatul stanga imi e asigurat de aint
      int pos = upper_bound(qrs[node].begin(), qrs[node].end(), y) -
                qrs[node].begin() - 1;
      tree[node].Update(0, pos, val);
      return; 
    }

    int mid = left + (right - left) / 2;
    if (x <= mid) {
      Update(2 * node + 1, left, mid, x, y, val);
    }
    if (mid < y) {
      Update(2 * node + 2, mid + 1, right, x, y, val);
    }
  }

  int Query(int node, int left, int right, int x, int y) {
    if (qrs[node].empty()) return 0;
    int pos = lower_bound(qrs[node].begin(), qrs[node].end(), y) -
              qrs[node].begin();
    int ans = tree[node].Query(pos);
    if (left == right) return ans;
    
    int mid = left + (right - left) / 2;
    if (x <= mid) {
      ans += Query(2 * node + 1, left, mid, x, y);
    } else {
      ans += Query(2 * node + 2, mid + 1, right, x, y);
    }
    return ans;
  }

  void AddQuery(int a, int b) {
    AddQuery(0, 0, n - 1, a, b);
  }

  void TurnOn(int l, int r, int t) {
    Update(0, 0, n - 1, l, r, -t);
  }

  void TurnOff(int l, int r, int t) {
    Update(0, 0, n - 1, l, r, +t);
  }

  int Query(int l, int r) {
    return Query(0, 0, n - 1, l, r); 
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, q; cin >> n >> q;
  string s; cin >> s;
  SegmTree st(n);
  vector<tuple<int, int, int>> qrs(q);
  for (auto &e : qrs) {
    string t; cin >> t;
    if (t[0] == 't') {
      int pos; cin >> pos; --pos;
      e = make_tuple(0, pos, -1);
    } else {
      int a, b; cin >> a >> b; --a, --b, --b;
      e = make_tuple(1, a, b);
      st.AddQuery(a, b);
    }
  }
  st.Build();

  set<pair<int, int>> ones;
  for (int i = 0; i < n; ) {
    if (s[i] == '0') {
      ++i;
    } else {
      int j = i;
      while (i < n && s[i] == '1') ++i;
      ones.emplace(j, i - 1);
    }
  }
   
  for (int t = 1; t <= q; ++t) {
    int type, x, y; tie(type, x, y) = qrs[t - 1];
    if (type == 0) {
      if (s[x] == '0') {
        int l = x, r = x;
        auto it = ones.lower_bound({x, 0});

        if (it != ones.begin()) {
          if (prev(it)->second == x - 1) {
            l = prev(it)->first;
            it = ones.erase(prev(it));
            st.TurnOff(l, x - 1, t);
          }
        }

        if (it != ones.end()) {
          if (it->first == x + 1) {
            r = it->second;
            ones.erase(it);
            st.TurnOff(x + 1, r, t);
          }
        }

        ones.emplace(l, r);
        st.TurnOn(l, r, t);
      } else {
        auto it = ones.upper_bound({x, n}); --it;
        assert(it->first <= x && x <= it->second);
        int l, r; tie(l, r) = *it;

        if (x != l) {
          ones.emplace(l, x - 1);
          st.TurnOn(l, x - 1, t);
        }
        if (x != r) {
          ones.emplace(x + 1, r);
          st.TurnOn(x + 1, r, t);
        }

        ones.erase(it);
        st.TurnOff(l, r, t);
      }
      s[x] ^= '0' ^ '1';
    } else {
      int ans = st.Query(x, y);
      auto it = ones.upper_bound({x, n});
      if (it != ones.begin()) {
        --it;
        assert(it->first <= x);
        if (it->second >= y) {
          ans += t;
        }
      }
      cout << ans << '\n';
    }
  }
}

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