Submission #1285158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285158		dex111222333444555	Matching (CEOI11_mat)	C++20	100 / 100	923 ms	39528 KiB

mat

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
template<class X, class Y> bool maximize (X &x, const Y &y) {return x < y ? x = y, 1 : 0;}
template<class X, class Y> bool minimize (X &x, const Y &y) {return x > y ? x = y, 1 : 0;}
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int base = 1e7 + 19;

int n, m;
int b[maxn];
int bpow[maxn];
pii st[4*maxn];

inline int mul(const int &a, const int &b)
{
    return (1LL * a * b) % MOD;
}

inline int add(const int &a, const int &b)
{
    int c = a + b;
    if (c >= MOD) c -= MOD;
    return c;
}

inline pii combine(const pii &a, const pii &b) {
  if (a.fi == 0) return b;
  if (b.fi == 0) return a;
  return {add(mul(a.fi, bpow[b.se]), b.fi), a.se + b.se};
}

void upd(int id, int l, int r, int u, pii val)
{
    if (l == r)
    {
        st[id] = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if (u <= mid) upd(id << 1, l, mid, u, val);
    else upd(id << 1 | 1, mid + 1, r, u, val);
    st[id] = combine(st[id << 1], st[id << 1 | 1]);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> m;

    int hsh = 0, up = 0;
    bpow[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        int x; cin >> x;
        hsh = add(mul(hsh, base), x);
        up = add(mul(up, base), 1);
    }

    vector<int> comp;
    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
        comp.pb(b[i]);
        bpow[i] = mul(bpow[i-1], base);
    }

    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());
    vector<int> ans;
    for (int i = 1; i <= m; ++i)
    {
        b[i] = lower_bound(all(comp), b[i]) - comp.begin() + 1;
        upd(1, 1, m, b[i], {i, 1});
        if (i > n) upd(1, 1, m, b[i-n], {0, 0});
        if (i >= n)
        {
            if (hsh == st[1].fi) ans.pb(i-n+1);
            hsh = add(hsh, up);
        }
    }
    cout << sz(ans) << '\n';
    for (auto i : ans) cout << i << ' ';
    return 0;
}

• 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