Submission #1184963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184963		HeartBreakKid	Matching (CEOI11_mat)	C++20	63 / 100	621 ms	67084 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"
ll size_pattern;
ll size_text;
ll k;
constexpr ll kMod = 1e9 + 7;
std::unordered_map<ll, ll> mp;
std::string s;
constexpr ll kBase = 37;
std::vector<ll> pows(1'000'005);

std::vector<std::pair<ll, ll>> tree((1 << 21) + 5);

void Update(const ll position, const ll value, const ll cur_ind = 1,
            const ll left = 1, const ll right = size_text) {
  if (left > position || right < position) {
    return;
  }
  if (left == right) {
    tree[cur_ind] = {value, value != 0};
    // value == 0 только если мы удаляем это число
    return;
  }
  ll 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 * 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 (ll i = 1; i <= 1000005; i++) {
    pows[i] = (pows[i - 1] * kBase) % kMod;
  }
  std::cin >> size_pattern >> size_text;
  std::vector<ll> pattern(size_pattern);

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

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

  for (ll i = 0; i < size_pattern; ++i) {
    Update(text[i], i + 1);
  }
  std::vector<ll> ans;
  for (ll 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