Submission #789064

#	Time	Username	Problem	Language	Result	Execution time	Memory
789064		tvladm2009	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	62 ms	6496 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 3e5 + 7;
int sol[107][107];
int n, q;
string s;

struct Operation {
  bool type;
  int a;
  int b;
};

vector<Operation> op;

int subtask() {
  if (n <= 100 && q <= 100) {
    return 1;
  }
  for (auto &it : op) {
    if (it.type == 1 && it.b - it.a != 1) {
      return 3;
    }
  }
  return 2;
}

int nodes = 0;

struct Dsu {
  struct History {
    int u;
    int v;
    int oldv;
    int oldszv;
  };

  vector<int> t, sz, par;
  vector<History> st;

  void init(int n) {
    t.resize(n + 1);
    sz.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      t[i] = i;
      sz[i] = 1;
    }
  }

  int root(int u) {
    assert(u <= 6);
    if (t[u] == u) {
      return u;
    }
    return root(t[u]);
  }

  void unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u != v) {
      if (sz[u] < sz[v]) {
        swap(u, v);
      }
      st.push_back({u, v, t[v], sz[v]});
      t[v] = u;
      sz[u] += sz[v];
    }
  }

  void undo() {
    History aux = st.back();
    st.pop_back();
    t[aux.v] = aux.oldv;
    sz[aux.v] = aux.oldszv;
    sz[aux.u] -= aux.oldszv;
  }
};

struct DynamicConectivity {
  vector<vector<pair<int, int>>> segt;
  Dsu dsu;

  void init(int q, int n) {
    segt.resize(4 * q + 1);
    dsu.init(n);
  }

  void update(int v, int tl, int tr, int x, int y, pair<int, int> edg) {
    if (tr < x || y < tl) {
      return;
    }
    if (x <= tl && tr <= y) {
      segt[v].push_back(edg);
      return;
    }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, x, y, edg);
    update(2 * v + 1, tm + 1, tr, x, y, edg);
  }

  void ins(int x, int y, pair<int, int> edg) {
    update(1, 1, q, x, y, edg);
  }

  vector<pair<int, int>> edges;

  void query(int v, int tl, int tr, int x, int y, int node, int &comp) {
    if (tr < x || y < tl) {
      return;
    }
    int undo = 0;
    /// cout << "! " << v << "\n";
    for (auto &edg : segt[v]) {
      /// cout << edg.first << " " << edg.second << "\n";
      if (dsu.root(edg.first) != dsu.root(edg.second)) {
        undo++;
        assert(edg.first <= 6 && edg.second <= 6);
        dsu.unite(edg.first, edg.second);
      }
    }
    if (x <= tl && tr <= y) {
      comp = dsu.root(node);
      /// for (auto &it : edges) {
        /// cout << it.first << " " << it.second << "\n";
      /// }
      /// cout << "\n";
    } else {
      int tm = (tl + tr) / 2;
      query(2 * v, tl, tm, x, y, node, comp);
      query(2 * v + 1, tm + 1, tr, x, y, node, comp);
    }
    while (undo--) {
      dsu.undo();
      edges.pop_back();
    }
  }

  void del(int n) {
    dsu.init(n);
  }
};

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

  // freopen("input", "r", stdin);

  cin >> n >> q >> s;
  s = "#" + s;
  for (int iq = 1; iq <= q; iq++) {
    string t;
    cin >> t;
    if (t == "toggle") {
      int a;
      cin >> a;
      op.push_back({0, a, -1});
    } else {
      int a, b;
      cin >> a >> b;
      op.push_back({1, a, b});
    }
  }
  if (subtask() == 1) {
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        int j = i;
        while (j <= n && s[j] == '1') {
          sol[i][j + 1]++;
          j++;
        }
      }
    }
    for (auto &it : op) {
      if (it.type == 1) {
        cout << sol[it.a][it.b] << "\n";
      } else {
        int pos = it.a;
        s[pos] ^= '0' ^ '1';
      }

      for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
          int j = i;
          while (j <= n && s[j] == '1') {
            sol[i][j + 1]++;
            j++;
          }
        }
      }
    }
    return 0;
  }
  if (subtask() == 2) {
    vector<vector<pair<int, int>>> active(n + 1);
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        active[i].push_back({0, -1});
      }
    }
    for (int i = 0; i < q; i++) {
      if (op[i].type == 0) {
        int pos = op[i].a;
        if (s[pos] == '0') {
          s[pos] = '1';
          active[pos].push_back({i + 1, -1});
        } else {
          s[pos] = '0';
          active[pos].back().second = i;
        }
      }
    }
    vector<vector<int>> sp(n + 1);
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        active[i].back().second = q;
      }
      if ((int) active[i].size() == 0) {
        continue;
      }
      sp[i].resize((int) active[i].size());
      sp[i][0] = active[i][0].second - active[i][0].first + 1;
      for (int j = 1; j < (int) active[i].size(); j++) {
        sp[i][j] = sp[i][j - 1] + active[i][j].second - active[i][j].first + 1;
      }
    }
    function<int(int, int)> get = [&](int pos, int t) {
      int low = 0, high = (int) active[pos].size() - 1, x = -1;
      while (low <= high) {
        int mid = (low + high) / 2;
        if (active[pos][mid].second <= t) {
          low = mid + 1;
          x = mid;
        } else {
          high = mid - 1;
        }
      }
      int sol = 0;
      if (x != -1) {
        sp[pos][x];
      }
      if (x + 1 < (int) active[pos].size() && active[pos][x + 1].first <= t) {
        sol += t - active[pos][x + 1].first + 1;
      }
      return sol;
    };
    for (int i = 0; i < q; i++) {
      if (op[i].type == 1) {
        assert(op[i].a + 1 == op[i].b);
        cout << get(op[i].a, i) << "\n";
      }
    }
    return 0;
  }
  if (subtask() == 3) {
    DynamicConectivity dc;
    dc.init(q + 1, n + 1);
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        dc.ins(1, q + 1, {i, i + 1});
      }
    }

    for (int i = 0; i < q; i++) {
      if (op[i].type == 0) {
        dc.ins(i + 2, q + 1, {op[i].a, op[i].a + 1});
      }
    }

    /// int comp = 0;
    /// dc.query(1, 1, q + 1, 1, 6, 4, comp);
    ///cout << comp << "\n";
    /// return 0;

    for (int i = 0; i < q; i++) {
      if (op[i].type == 1) {
        int a = op[i].a;
        int b = op[i].b;
        int low = 1, high = i + 2, sol = -1;
        while (low <= high) {
          int mid = (low + high) / 2;
          int compa = 0, compb = 0;
          dc.query(1, 1, q + 1, 1, mid, a, compa);
          dc.query(1, 1, q + 1, 1, mid, b, compb);
          /// cout << mid << " " << a << " " << b << " => " << compa << " " << compb << "\n";
          if (compa == compb) {
            sol = mid;
            high = mid - 1;
          } else {
            low = mid + 1;
          }
        }
        if (sol == -1) {
          cout << "0\n";
        } else {
          cout << i + 2 - sol << "\n";
          /// cout << i << " " << sol << "\n";
        }
      }
    }
    return 0;
  }
  return 0;
}

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