Submission #1184974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184974		HeartBreakKid	Matching (CEOI11_mat)	C++20	63 / 100	398 ms	31316 KiB

mat

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pk pop_back
#define yes std::cout << "YES\n"
#define no std::cout << "NO\n"
int size_pattern;
int size_text;
int k;
constexpr int kMod = 1e9 + 7;
std::unordered_map<int, int> mp;
std::string s;
constexpr int kBase = 37;
int pows[1'000'005];

std::pair<int, int> tree[2'000'000 + 5];
std::pair<int, int> for_compress[1'000'000 + 5];

void Update(int position, int value,
            int cur_ind = 1, int left = 1,
            int right = size_text) {
  if (left > position || right < position) {
    return;
  }
  if (left == right) {
    tree[cur_ind] = {value, value != 0};
    // value == 0 только если мы удаляем это число
    return;
  }
  int mid = (left + right) >> 1;

  Update(position, value, cur_ind * 2, left, mid);
  Update(position, value, cur_ind * 2 + 1, mid + 1, right);

  tree[cur_ind].second =
      tree[cur_ind * 2].second + tree[cur_ind * 2 + 1].second;
  tree[cur_ind].first = (tree[cur_ind * 2].first * 1LL *
                             pows[tree[cur_ind * 2 + 1].second] % kMod +
                         tree[cur_ind * 2 + 1].first) %
                        kMod;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  pows[0] = 1;
  for (int i = 1; i <= 1000000; i++) {
    pows[i] = (pows[i - 1] * 1LL * kBase) % kMod;
  }
  std::cin >> size_pattern >> size_text;
  std::vector<int> pattern(size_pattern);

  int hash_to_add{};
  int need_hash{};
  for (int i = 0; i < size_pattern; ++i) {
    std::cin >> pattern[i];
    hash_to_add = (hash_to_add + 0LL + pows[i]) % kMod;
    need_hash = (need_hash * 1LL * kBase + pattern[i]) % kMod;
  }

  for (int i = 0; i < size_text; ++i) {
    std::cin >> for_compress[i].first;
    for_compress[i].second = i;
  }
  std::sort(for_compress, for_compress + size_text);
  std::vector<int> text(size_text);
  for (int i = 0; i < size_text; ++i) {
    text[for_compress[i].second] = i + 1;
  }

  for (int i = 0; i < size_pattern; ++i) {
    Update(text[i], i + 1);
  }
  std::vector<int> ans;
  for (int i = size_pattern; i < size_text; ++i) {
    // std::cout << tree[1].first << " " << need_hash << std::endl;
    if (tree[1].first == need_hash) {
      ans.push_back(i - size_pattern + 1);
    }
    Update(text[i - size_pattern], 0);
    Update(text[i], i + 1);
    need_hash += hash_to_add;
    need_hash %= kMod;
  }
  if (tree[1].first == need_hash) {
    ans.push_back(size_text - size_pattern + 1);
  }
  std::cout << ans.size() << '\n';
  for (auto ind : ans) {
    std::cout << ind << ' ';
  }
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10