oj.uz

Submission #966787

# Submission time Handle Problem Language Result Execution time Memory
966787 2024-04-20T11:03:57 Z kilkuwu Street Lamps (APIO19_street_lamps) C++17
20 / 100
 849 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 399 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 349 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 525 ms 59064 KB Output is correct
6 Correct 691 ms 66780 KB Output is correct
7 Correct 837 ms 73556 KB Output is correct
8 Correct 849 ms 83572 KB Output is correct
9 Correct 76 ms 7248 KB Output is correct
10 Correct 82 ms 7784 KB Output is correct
11 Correct 86 ms 8500 KB Output is correct
12 Correct 280 ms 81900 KB Output is correct
13 Correct 825 ms 83672 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Runtime error 307 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 399 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -