Submission #739487

#	Time	Username	Problem	Language	Result	Execution time	Memory
739487		jelly1010	Matching (CEOI11_mat)	C++14	36 / 100	220 ms	65536 KiB

mat

#include <bits/stdc++.h>

#define lli long long
#define fi first
#define se second
#define maxi(a, b) a = max(a, b)
#define mize(a, b) a = min(a, b)
#define getbit(a, i) ((a) >> (i) & 1)

#define FOR(i, a, b) for(int i=a, _n=b; i<=_n; ++i)
#define FORD(i, a, b) for(int i=a, _n=b; i>=_n; --i)
#define REP(i, _n) for(int i=0; i<_n; ++i)

#define sz(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair

#define ii pair<int, int>

using namespace std;

typedef long long hash_type;

const int N = 2e5+5;
const hash_type MOD = 1e9+7;

int n, q;
string s;
hash_type it1[N*4], it2[N*4], bs[N];
// it1 - left to right, left * base + right
// it2 - right to left, right * base + left

template <typename T, int SZ>
struct PST {
    struct Node {
        T val;
        int c[2];
        Node() {
            val = 0;
            c[0] = c[1] = 0;
        }
    };
    static const int LIM = 5e6;
    Node d[LIM];
    int nxt = 0;
    int copy(int t) { d[nxt] = d[t]; return nxt++; }
    T comb(const T& a, const T& b) { return a + b; }
    void pull(int c) { d[c].val = comb(d[d[c].c[0]].val, d[d[c].c[1]].val); }
    T query(int lo, int hi, int t, int l, int r) {
        if (lo >= r || hi <= l) return 0;
        if (lo <= l && r <= hi) return d[t].val;
        int m = (l + r) / 2;
        T lef = query(lo, hi, d[t].c[0], l, m);
        T rig = query(lo, hi, d[t].c[1], m, r);
        return comb(lef, rig);
    }
    int upd(int i, const T& v, int t, int l, int r) {
        int x = copy(t);
        if (r - l == 1) {
            d[x].val = v;
            return x;
        }
        int m = (l + r) / 2;
        if (i < m) {
            d[x].c[0] = upd(i, v, d[x].c[0], l, m);
        }else{
            d[x].c[1] = upd(i, v, d[x].c[1], m, r);
        }
        pull(x);
        return x;
    }
    int build(const vector<T>& a, int l, int r) {
        int c = nxt++;
        if (r - l == 1) {
            if (l < (int)a.size()) d[c].val = a[l];
            return c;
        }
        int m = (l + r) / 2;
        d[c].c[0] = build(a, l, m);
        d[c].c[1] = build(a, m, r);
        pull(c);
        return c;
    }
    vector<int> rts;
    void update_time(int i, const T& v) {
        rts.pb(upd(i, v, rts.back(), 0, SZ));
    }
    void build(const vector<T>& a) {
        rts.pb(build(a, 0, SZ));
    }
    T query_time(int ti, int lo, int hi) {
        return query(lo, hi, rts[ti], 0, SZ);
    }

    int order_of(int t1, int t2, int x, int l, int r) {
      //gets count <=
      if (r - l == 1) {
        if (l > x) return 0;
        return d[t1].val - d[t2].val;
      }
      int m = (l + r) / 2;
      if (x < m) {
        return order_of(d[t1].c[0], d[t2].c[0], x, l, m);
      }
      int on_left = d[d[t1].c[0]].val - d[d[t2].c[0]].val;
      return on_left + order_of(d[t1].c[1], d[t2].c[1], x, m, r);
    }

    int order_of(int t1, int t2, int x) {
      int ret = order_of(rts[t1], rts[t2], x, 0, SZ);
      return ret;
    }
};
PST<int, 1 << 20> pst;

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<int> c = a;
  for (int i = 0; i < n; i++) {
    c[a[i]] = i;
  }
  a = c;
  for (auto& u : a) u++;

  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> fen(n + 1);
  auto prefix = [&](int g) -> int {
    int ret = 0;
    for (; g > 0; g -= g & -g)
      ret += fen[g];
    return ret;
  };

  auto up_fen = [&](int g) -> void {
    for (; g <= n; g += g&-g)
      fen[g] += 1;
  };

  vector<int> order_stat(n);
  for (int i = 0; i < n; i++) {
    order_stat[i] = prefix(a[i]);
    up_fen(a[i]);
  }

  #ifdef LOCAL
  cout << "A:\n";
  for (auto u : a)
   cout << u << " ";
   cout << "\n";
  cout << "Order stat:\n";
  for (auto u : order_stat)
    cout << u << " ";
  cout << "\n";
  cout << "\n";
  #endif

  pst.build(vector<int>(n + 1, 0));
  int original_root = (int)pst.rts.size() - 1;
  vector<int> root_times(n);
  auto order_of = [&](int l, int r, int x) -> int {
    int ret = pst.order_of(root_times[r], (l ? root_times[l - 1] : original_root), x);
    return ret;
  };

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

      j = kmp[j - 1];
    }
    pst.update_time(a[i], 1);
    root_times[i] = (int)pst.rts.size() - 1;
  }

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

  pst.rts.clear();
  pst.nxt = 0;
  pst.build(vector<int>(m + 1, 0));
  original_root = (int)pst.rts.size() - 1;
  root_times = vector<int>(m, 0);

  vector<int> kmp_b(m);
  vector<int> ans;
  int prev_kmp = 0;
  for (int i = 0; i < m; i++) {
    int j = prev_kmp;
    while (j >= 0) {
      if (j != n and (j == 0 or order_of(i - j, i - 1, b[i]) == order_stat[j])) {
        kmp_b[i] = j + 1;
        break;
      }
      j = kmp[j - 1];
    }

    pst.update_time(b[i], 1);
    root_times[i] = (int)pst.rts.size() - 1;
    prev_kmp = kmp_b[i];
    if (kmp_b[i] == n) {
      ans.pb(i);
    }
  }

  #ifdef LOCAL
  cout << "B KMP: ";
  for (auto u : kmp_b)
    cout << u << " ";
  cout << "\n";
  #endif

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

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