Submission #712143

#	Time	Username	Problem	Language	Result	Execution time	Memory
712143		badont	Matching (CEOI11_mat)	C++17	100 / 100	1150 ms	39492 KiB

mat

#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<numeric>
using namespace std;
using ll = long long;

#define all(x) x.begin(), x.end()
#define pb push_back

constexpr int INF = 1e9;
int zero_val = INF;

struct Max {
  int operator()(const int& a, const int& b) {
    return max(a, b);
  }
};

struct Min {
  int operator()(const int& a, const int& b) {
    return min(a, b);
  }
};


template<typename T, typename Merge> 
struct seg {
  Merge merge;
  int n;
  vector<T> tr;

  seg(int n) : merge(Merge()), n(n), tr(2 * n + 1, zero_val) {}
  seg(const vector<T>& a) : seg((int)a.size()) {
    for (int i = n; i < 2 * n; i++) {
      tr[i] = a[i - n];
    }
    for (int i = n - 1; i >= 1; i--) {
      tr[i] = merge(tr[2 * i], tr[2 * i] + 1);
    }
  }

  void upd(int g, const T& k) {
    for (tr[g += n] = k; g > 1; g /= 2) {
      tr[g / 2] = merge(tr[g], tr[g ^ 1]);
    }
  }

  T query(int l, int r) {
    r++;
    T res = zero_val;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) res = merge(res, tr[l++]);
      if (r & 1) res = merge(res, tr[--r]);
    }
    return res;
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;

  vector<int> a(n), b(m);
  for (auto& u : a) {
    cin >> u;
    u--;
  }
  vector c = a;
  for (int i = 0; i < n; i++) {
    c[a[i]] = i;
  }
  a = c;
  for (auto& u : b)
    cin >> u;

  c = b;
  sort(all(c));
  c.erase(unique(all(c)), c.end());
  for (auto& u : b) {
    u = lower_bound(all(c), u) - c.begin();
  }
  c.clear();

  vector<int> order(n);
  iota(all(order), 0);

  sort(all(order), [&](int i, int j) {
    return a[i] < a[j];
  });

  vector<int> a_inv(a);
  for (int i = 0; i < n; i++) {
    a_inv[a[i]] = i;
  }
 
  vector<int> less_under(n), great_under(n); 
  {
    zero_val = -INF;
    seg<int, Max> tree(vector<int>(n, -INF)); 
    for (const auto& idx : order) {
      less_under[idx] = tree.query(0, idx - 1);
      tree.upd(idx, a[idx]);
    }
    for (int i = 0; i < n; i++) {
      if (less_under[i] < 0) {
        less_under[i] = -1;
      } else {
        assert(less_under[i] >= 0 and less_under[i] < n);
        less_under[i] = a_inv[less_under[i]];
      } 
    }
  }

  {
    reverse(all(order));
    zero_val = INF;
    seg<int, Min> tree(vector<int>(n, INF)); 
    for (const auto& idx : order) {
      great_under[idx] = tree.query(0, idx - 1);
      tree.upd(idx, a[idx]);
    }
    for (int i = 0; i < n; i++) {
      if (great_under[i] >= n) {
        great_under[i] = -1;
      } else {
        assert(great_under[i] >= 0 and great_under[i] < n);
        great_under[i] = a_inv[great_under[i]];
      } 
    } 
  }
  
  a_inv.clear();

  #ifdef LOCAL
  cout << "A after processing: "; for (auto u : a) cout << u << " "; cout << "\n";
  #endif

  #ifdef LOCAL
  cout << "less under: "; for (auto u : less_under) cout << u << " "; cout << "\n";
  cout << "great under: "; for (auto u : great_under) cout << u << " "; cout << "\n";
  #endif

  order.clear();

  auto check_kmp = [&](int end_idx, int j, const vector<int>& a) -> bool {
    assert(j >= 1);
    int less_under_idx = less_under[j - 1];
    if (less_under_idx != -1) {
      int less_dist = j - 1 - less_under_idx;
      assert(end_idx < (int)a.size() and end_idx >= 0);
      assert(less_dist <= end_idx);
      
      if (a[end_idx] < a[end_idx - less_dist]) {
        return false;
      }
    }
    int great_under_idx = great_under[j - 1];
    if (great_under_idx != -1) {
      int great_dist = j - 1 - great_under_idx;
      assert(end_idx < (int)a.size() and end_idx >= 0);
      assert(great_dist <= end_idx);
      if (a[end_idx] > a[end_idx - great_dist]) {
        return false;
      }
    }

    return true;
  };

  vector<int> kmp(n);
  for (int i = 1; i < n; i++) {
    int j = kmp[i - 1];
    while (j >= 0) {
      //check j + 1
      if (check_kmp(i, j + 1, a)) {
        kmp[i] = j + 1;
        break;
      } 
      if (j == 0) break;
      j = kmp[j - 1];
    }
  }
  a.clear();

  #ifdef LOCAL
  cout << "A KMP: ";
  for (auto u : kmp) cout << u << " ";
  cout << '\n';
  #endif

  vector<int> ans;
  int prev_kmp = 0;
  for (int i = 0; i < m; i++) {
    int j = prev_kmp;
    int cur_kmp = 0;
    while (j >= 0) {
      if (check_kmp(i, j + 1, b)) {
        cur_kmp = j + 1;
        break;
      }
      if (j == 0) break;
      j = kmp[j - 1];
    }

    prev_kmp = cur_kmp;
    if (cur_kmp == n) {
      ans.pb(i);
    }
  }

  
  cout << ans.size() << "\n";
  for (auto u : ans)
    cout << u + 1 - n + 1 << " ";
  cout << '\n';
};

• 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: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10