Submission #789066

#	Time	Username	Problem	Language	Result	Execution time	Memory
789066		tvladm2009	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	151 ms	38992 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 { /// partially persistent dsu
  vector<vector<pair<int, int>>> par;
  int time = 0;
  DSU(int n) : par(n + 1, {{-1, 0}}) {

  }

  bool unite(int u, int v) {
    time++;
    if ((u = root(u, time)) == (v = root(v, time))) return 0;
    if (par[u].back().first > par[v].back().first) {
      swap(u, v);
    }
    par[u].push_back({par[u].back().first + par[v].back().first, time});
    par[v].push_back({u, time});
    return 1;
  }

  bool same(int u, int v, int t) {
    return root(u, t) == root(v, t);
  }

  int root(int u, int t) { /// root of u at time t
    if (par[u].back().first >= 0 && par[u].back().second <= t) {
      return root(par[u].back().first, t);
    }
    return u;
  }

  int size(int u, int t) { /// size of the component of u at time t
    u = root(u, t);
    int low = 0, high = (int) par[u].size() - 1, ans = 0;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (par[u][mid].second <= t) {
        ans = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return -par[u][ans].first;
  }
};

int a[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) {
        sol += 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) {
    DSU t(n + 1);
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        t.unite(i, i + 1);
        a[t.time] = 1;
      }
    }
    for (int i = 2; i <= q + 1; i++) {
      if (op[i - 2].type == 0) {
        t.unite(op[i - 2].a, op[i - 2].a + 1);
        a[t.time] = i;
      } else {
        int low = 1, high = i, sol = -1;
        while (low <= high) {
          int mid = (low + high) / 2;
          if (t.same(op[i - 2].a, op[i - 2].b, mid)) {
            sol = a[mid];
            high = mid - 1;
          } else {
            low = mid + 1;
          }
        }
        if (sol == -1) {
          cout << "0\n";
        } else {
          cout << i - sol << "\n";
        }
      }
    }
    return 0;
  }
  return 0;
}

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