Submission #966787

#	Time	Username	Problem	Language	Result	Execution time	Memory
966787		kilkuwu	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	849 ms	524288 KiB

street_lamps

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, q;
  std::cin >> n >> q;

  std::string s;
  std::cin >> s;

  std::vector<std::set<int>> adj(n + 1);

  std::map<std::pair<int, int>, int> when;

  std::vector<std::array<int, 3>> queries(q + 1);
  std::vector<std::pair<int, int>> toggle_on;
  for (int i = 1; i <= q; i++) {
    std::string com;
    std::cin >> com;
    queries[i][0] = com == "toggle";
    if (queries[i][0]) {
      int id;
      std::cin >> id;
      queries[i][1] = --id;
      toggle_on.emplace_back(id, i);
    } else {
      int a,b ;
      std::cin >> a >> b;
      queries[i][1] = --a;
      queries[i][2] = --b;
      adj[a].insert(b);
      adj[b].insert(a);
    }
  }

  std::vector<std::set<int>> elem(n + 1);
  std::vector<int> e(n + 1, -1);
  for (int i = 0; i <= n; i++) {
    elem[i].insert(i);
  }

  std::function<int(int)> find = [&](int u) {
    return e[u] < 0 ? u : e[u] = find(e[u]);
  };

  auto mark = [&](int x, int y, int t) {
    if (x > y) std::swap(x, y);
    when[{x, y}] = t;
  };

  auto join = [&](int t, int u, int v) {
    u = find(u);
    v = find(v);
    if (e[u] > e[v]) std::swap(u, v);
    e[u] += e[v];
    e[v] = u;
    int lu = *elem[u].begin();
    int ru = *elem[u].rbegin();
    for (int x : elem[v]) {
      auto it = adj[x].lower_bound(lu);
      while (it != adj[x].end() && *it <= ru) {
        int y = *it;
        mark(x, y, t);
        adj[y].erase(x);
        it = adj[x].erase(it);
      }
    }
    elem[u].insert(elem[v].begin(), elem[v].end());
    elem[v].clear();
  };

  for (int i = 0; i < n; i++) {
    if (s[i] == '1') join(0, i, i + 1);
  }

  for (auto [id, t] : toggle_on) {
    join(t, id, id + 1);
  }

  dbg(when);
  for (int tt = 1; tt <= q; tt++) {
    if (queries[tt][0] == 0) {
      auto [x, y, z] = queries[tt];
      auto it = when.find({y, z});
      int start = 0;
      if (it == when.end()) {
        start = 1e9;
      } else {
        start = it->second;
      }
      if (tt < start) {
        std::cout << 0 << nl;
      } else {
        std::cout << tt - start << nl;
      }
    }
  }

}

/*
5 7
11011
query 3 4
toggle 3
query 3 4 
query 1 2 
toggle 1
query 3 4 
query 1 2 
*/

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