Submission #830851

#	Time	Username	Problem	Language	Result	Execution time	Memory
830851		trytovoi	Matching (CEOI11_mat)	C++14	100 / 100	1170 ms	43504 KiB

mat

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for(int i = 0, ____n = (n); i < ____n; ++i)
#define all(x) (x).begin(), (x).end()

const int MX = (int) 1e6 + 5;

const int NMOD = 2;
const int mod = (int) 1e9 + 7;
const int BASE = MX + 2;

void add(int& x, int y) {
    if ((x += y) >= mod) x -= mod;
}
int sadd(int x, int y) {
    add(x, y);
    return x;
}
void sub(int& x, int y) {
    if ((x -= y) < 0) x += mod;
}
int ssub(int x, int y) {
    sub(x, y);
    return x;
}

int n, m;
int a[MX], aa[MX], b[MX], c[MX];
int pw[MX], prefix[MX];

class segtree {
 public:
  struct node {
    int val = 0;
    int cnt = 0;
 
    void apply(int l, int r, int v) {
      if (v == -1) val = cnt = 0;
      else {
          val = v;
          cnt = 1;
      }
    }
  };
 
  node unite(const node &a, const node &b) const {
    node res;
    res.cnt = a.cnt + b.cnt;
    res.val = sadd(a.val, (1LL * pw[a.cnt] * b.val % mod));
    return res;
  }
 
  inline void push(int x, int l, int r) {
  }
 
  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }
 
  int n;
  vector<node> tree;
 
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
 
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }
 
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
 
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
 
  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
 
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
 
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }
 
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
 
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
 
  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
 
  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once
 
  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
 
  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("MOHINHGIA.inp", "r", stdin);
    // freopen("MOHINHGIA.out", "w", stdout);
    cin >> n >> m;
    pw[0] = 1;
    prefix[0] = 1;
    for (int i = 1; i <= n; ++i) {
        pw[i] = 1LL * pw[i - 1] * BASE % mod;
        prefix[i] = sadd(prefix[i - 1], pw[i]);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        aa[a[i]] = i;
    }
    for (int i = 1; i <= n; ++i) c[aa[i]] = i;
    int hashA = 0;
    for (int i = 1; i <= n; ++i) add(hashA, 1LL * pw[i - 1] * c[i] % mod);
    vector<int> vec;
    for (int i = 1; i <= m; ++i) {
        cin >> b[i];
        vec.push_back(b[i]);
    }
    sort(all(vec));
    for (int i = 1; i <= m; ++i) 
        b[i] = lower_bound(all(vec), b[i]) - vec.begin() + 1;
    segtree st(m + 1);
    for (int i = 1; i <= n; ++i) {
        int ind = b[i], val = i;
        st.modify<int>(ind, ind, val);
    }
    vector<int> ans;
    if (st.get(1, m).val == hashA) ans.push_back(1);
    for (int i = 2; i <= m - n + 1; ++i) {
        int ind = b[i - 1], val = -1;
        st.modify<int>(ind, ind, val);
        ind = b[i + n - 1], val = i + n - 1;
        st.modify<int>(ind, ind, val);
        add(hashA, prefix[n - 1]);
        if (hashA == st.get(1, m).val) ans.push_back(i);
    }
    cout << (int) ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
    return 0;
}

/**
6 12
2 5 3 4 1 6
10 45 25 30 5 47 31 35 4 50 33 20

5 1 3 4 2 6
BASE^0 * 5 + BASE^1 * 1 + BASE^2 * 3 + BASE^3 * 4 + BASE^4 * 2 + BASE^5 * 6

10 45 25 30 5 47
=> 5 1 3 4 2 6

5 6  7  8  9 10
5 47 31 35 4 50
=> 9 5 7 8 6 10
BASE^0 * 9 + BASE^1 * 5 + BASE^2 * 7 + BASE^3 * 8 + BASE^4 * 6 + BASE^5 * 10


4 6
1 3 4 2 
29 43 2 23 43 9 

1 4 2 3

1 * BASE^0 + 4 * BASE^1 + 2 * BASE^2 + 3 * BASE^3

3 4  5  6
2 23 43 9 
=> 3 6 4 5

3 * BASE^0 + 6 * BASE^1 + 4 * BASE^2 + 5 * BASE^3

**/

• 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