Submission #522306

#	Time	Username	Problem	Language	Result	Execution time	Memory
522306		SuffixAutomata	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5058 ms	434936 KiB

street_lamps

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll

const int MOD = 1000000007;

int n;
int trr[300005];
struct lin {
  int k, b;
  const lin operator+(const lin &o) const { return {k + o.k, b + o.b}; }
} s[3 << 22];
int lc[3 << 22], rc[3 << 22];
int _stt = 1;

void modif(int &idx, int u, lin d, int l = 0, int r = n + 1) {
  if (!(l <= u && u < r))
    return;
  if (!idx)
    idx = _stt++;
  if (r - l == 1) {
    s[idx] = s[idx] + d;
    return;
  }
  modif(lc[idx], u, d, l, (l + r) / 2);
  modif(rc[idx], u, d, (l + r) / 2, r);
  s[idx] = s[lc[idx]] + s[rc[idx]];
}
lin nsbasket(int idx, int L, int R, int l = 0, int r = n + 1) {
  if (!idx || R <= l || r <= L)
    return {0, 0};
  if (L <= l && r <= R)
    return s[idx];
  return nsbasket(lc[idx], L, R, l, (l + r) / 2) +
         nsbasket(rc[idx], L, R, (l + r) / 2, r);
}

void add(int i, int j, lin r) {
  i++;
  while (i <= n + 2) {
    modif(trr[i], j, r);
    i += (i & (-i));
  }
}
lin qry(int i, int j) {
  i++;
  lin ans = {0, 0};
  while (i) {
    ans = ans + nsbasket(trr[i], 0, j + 1);
    i -= (i & (-i));
  }
  return ans;
}

int T;
void toggle(int l, int r, int f) {
  if (l > r)
    return;
  lin yes = {1, -T}, no = {-1, T};
  if (f == -1)
    swap(yes, no);
  add(l, l, yes), add(l, r + 1, no), add(r + 1, l, no), add(r + 1, r + 1, yes);
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<int> zp;
  zp.insert(-1), zp.insert(n);
  for (int i = 0; i < n; i++)
    if (s[i] == '0')
      zp.insert(i);
  {
    auto s = zp.begin();
    while (s != zp.end()) {
      if (*s != -1)
        toggle(*prev(s) + 1, *s - 1, 1);
      s = next(s);
    }
  }
  for (T = 1; T <= q; T++) {
    string op;
    cin >> op;
    if (op == "toggle") {
      int i;
      cin >> i;
      auto q = zp.find(--i);
      if (q != zp.end()) {
        toggle(*prev(q) + 1, i - 1, -1);
        toggle(i + 1, *next(q) - 1, -1);
        toggle(*prev(q) + 1, *next(q) - 1, 1);
        zp.erase(q);
      } else {
        q = zp.insert(i).first;
        toggle(*prev(q) + 1, *next(q) - 1, -1);
        toggle(*prev(q) + 1, i - 1, 1);
        toggle(i + 1, *next(q) - 1, 1);
      }
    } else {
      int l, r;
      cin >> l >> r;
      lin ans = qry(l - 1, r - 2);
      cout << T * ans.k + ans.b << endl;
    }
  }
}

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