제출 #1285055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285055		peanut	Matching (CEOI11_mat)	C++20	100 / 100	1742 ms	51984 KiB

mat

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#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 a[maxn], b[maxn];
pii st[4*maxn];

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

pii combine(pii a, pii b)
{
    return make_pair(1LL * ((a.fi * binpow(base, b.se)) % MOD + b.fi) % MOD, 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*2, l, mid, u, val);
    else upd(id*2+1, mid+1, r, u, val);
    st[id] = combine(st[id*2], st[id*2+1]);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> m;

    ll h = 0, up = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        h = (h * base + a[i]) % MOD;
        up = (up * base + 1) % MOD;
    }

    vector<int> comp;
    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
        comp.pb(b[i]);
    }
    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});
        //cout << b[i] << ' ';
        if (i > n) upd(1, 1, m, b[i-n], {0, 0});
        if (i >= n)
        {
            if (h == st[1].fi) ans.pb(i-n+1);
            h = (h + up) % MOD;
        }
        //cout << st[1].fi << '\n';
    }
    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