제출 #1239606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239606		avighna	I want to be the very best too! (NOI17_pokemonmaster)	C++20	11 / 100	96 ms	3772 KiB

pokemonmaster

#include <bits/stdc++.h>

int main() {
  int r, c, q;
  std::cin >> r >> c >> q;
  assert(r == 1);
  
  std::vector<std::pair<int, std::pair<int, int>>> l;
  for (int i = 0; i < r; ++i) {
    for (int j = 0, x; j < c; ++j) {
      std::cin >> x;
      l.push_back({x, {i, j}});
    }
  }

  std::vector type(r, std::vector<int>(c));
  for (auto &i : type) {
    for (int &j : i) {
      std::cin >> 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;
  auto &a = type[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;
      assert(y == 0);
      times.push_back({x, a[x], p});
    } else {
      int x, y, l;
      std::cin >> x >> y >> l;
      --x, --y, --l;
      assert(y == 0);
      if (x <= l) {
        queries.push_back({0, std::min(l, c - 1), 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 = 0, 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: 0 / 24
• Subtask 5: 0 / 29