Submission #1239747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239747		avighna	I want to be the very best too! (NOI17_pokemonmaster)	C++20	35 / 100	1759 ms	15172 KiB

pokemonmaster

#include <bits/stdc++.h>

class UFDS {
public:
  int n;
  std::vector<int> par;

  UFDS(int n) : n(n), par(n) {
    std::iota(par.begin(), par.end(), 0);
  }

  int root(int u) {
    return u == par[u] ? u : par[u] = root(par[u]);
  }

  void merge(int u, int v) {
    u = root(u), v = root(v);
    if (u != v) {
      par[v] = u;
    }
  }
};

int main() {
  int r, c, q;
  std::cin >> r >> c >> q;
  
  std::vector<std::pair<int, std::pair<int, int>>> l;
  std::vector<int> real(r * c);
  for (int i = 0; i < r; ++i) {
    for (int j = 0, x; j < c; ++j) {
      std::cin >> x;
      l.push_back({x, {i, j}});
      real[i * c + j] = x;
    }
  }
  std::sort(l.begin(), l.end());
  UFDS dsu(r * c);
  std::vector vis(r, std::vector<bool>(c));
  std::array<int, 4> disp_x = {1, -1, 0, 0}, disp_y = {0, 0, 1, -1};
  std::vector<int> par(r * c);
  std::iota(par.begin(), par.end(), 0);
  for (int i = 0; i < r * c; ++i) {
    auto &[x, y] = l[i].second;
    vis[x][y] = true;
    int cur = x * c + y;
    for (int j = 0; j < 4; ++j) {
      int n_x = x + disp_x[j], n_y = y + disp_y[j];
      if (n_x < 0 or n_y < 0 or n_x >= r or n_y >= c or !vis[n_x][n_y]) {
        continue;
      }
      par[dsu.root(n_x * c + n_y)] = cur;
      dsu.merge(cur, n_x * c + n_y);
    }
  }
  const int w = std::bit_width(uint32_t(r * c));
  std::vector lift(r * c, std::vector<int>(w));
  std::vector<std::vector<int>> adj(r * c);
  for (int i = 0; i < r * c; ++i) {
    lift[i][0] = par[i];
    if (i != par[i]) {
      adj[par[i]].push_back(i);
    }
  }
  for (int i = 1; i < w; ++i) {
    for (int j = 0; j < r * c; ++j) {
      lift[j][i] = lift[lift[j][i - 1]][i - 1];
    }
  }
  std::vector<int> start(r * c), end(r * c);
  int timer = 0;
  auto dfs = [&](auto &&self, int u) -> void {
    start[u] = timer++;
    for (int &i : adj[u]) {
      self(self, i);
    }
    end[u] = timer - 1;
  };
  dfs(dfs, l.back().second.first * c + l.back().second.second);

  std::vector<int> a(r * c);
  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      std::cin >> a[start[i * c + j]];
    }
  }

  struct time {
    int i, before, after;
  };
  struct query {
    int l, r, t, idx;
  };
  std::vector<time> times;
  std::vector<query> queries;
  int tot_queries = 0;
  for (int i = 0, t; i < q; ++i) {
    std::cin >> t;
    if (t == 1) {
      int x, y, p;
      std::cin >> x >> y >> p;
      --x, --y;
      int idx = start[y * c + x];
      times.push_back({idx, a[idx], p});
      a[idx] = p;
    } else {
      int x, y, l;
      std::cin >> x >> y >> l;
      --x, --y;
      int u = y * c + x;
      if (real[u] <= l) {
        for (int bt = w - 1; bt >= 0; --bt) {
          if (real[lift[u][bt]] <= l) {
            u = lift[u][bt];
          }
        }
        queries.push_back({start[u], end[u], int(times.size()), tot_queries});
      }
      tot_queries++;
    }
  }

  const int B = std::pow(times.size() * c * c / double(2 * queries.size()), double(1) / 3);
  std::sort(queries.begin(), queries.end(), [&](query q1, query q2) {
    if (q1.l / B != q2.l / B) {
      return q1.l / B < q2.l / B;
    }
    if (q1.r / B != q2.r / B) {
      return q1.r / B < q2.r / B;
    }
    return q1.t < q2.t;
  });
  int cur_l = 0, cur_r = -1, cur_t = times.size(), cur_ans = 0;
  std::vector<int> cnt(50001);
  std::vector<int> ans(tot_queries);
  for (auto &[l, r, t, idx] : queries) {
    while (cur_r < r) {
      cur_ans += cnt[a[++cur_r]]++ == 0;
    }
    while (r < cur_r) {
      cur_ans -= cnt[a[cur_r--]]-- == 1;
    }
    while (cur_l < l) {
      cur_ans -= cnt[a[cur_l++]]-- == 1;
    }
    while (l < cur_l) {
      cur_ans += cnt[a[--cur_l]]++ == 0;
    }
    while (cur_t < t) {
      auto [i, bef, aft] = times[cur_t++];
      if (cur_l <= i and i <= cur_r) {
        cur_ans -= cnt[a[i]]-- == 1;
        cur_ans += cnt[a[i] = aft]++ == 0;
      } else {
        a[i] = aft;
      }
    }
    while (t < cur_t) {
      auto [i, bef, aft] = times[--cur_t];
      if (cur_l <= i and i <= cur_r) {
        cur_ans -= cnt[a[i]]-- == 1;
        cur_ans += cnt[a[i] = bef]++ == 0;
      } else {
        a[i] = bef;
      }
    }
    ans[idx] = cur_ans;
  }

  for (int &i : ans) {
    std::cout << i << '\n';
  }
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 29