제출 #1221579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221579		DangKhoizzzz	Matching (CEOI11_mat)	C++20	0 / 100	676 ms	89004 KiB

mat

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 9;
const int base = 1e6 + 7;

int power[maxn];

struct node
{
    int hsh , cnt;

    node()
    {
        hsh = 0 , cnt = 0;
    }
};

node merging (node L , node R)
{
    node res;
    res.cnt = L.cnt + R.cnt;
    res.hsh = (L.hsh*power[R.cnt] + R.hsh)%mod;
    return res;
}

node st[maxn*4];

void update(int id , int l , int r , int pos , int val , int c)
{
    if(l > pos || r < pos) return;
    if(l == r)
    {
        st[id].hsh = val;
        st[id].cnt = c;
        return;
    }
    int mid = (l+r) >> 1;
    update(id*2 , l , mid , pos , val , c);
    update(id*2+1 , mid+1 , r , pos , val , c);
    st[id] = merging(st[id*2] , st[id*2+1]);
}

int n , m , a[maxn] , b[maxn];

void compress()
{
    vector <int> val;
    for(int i = 1; i <= m; i++) val.push_back(b[i]);
    sort(val.begin() , val.end());
    for(int i = 1; i <= m; i++)
    {
        b[i] = upper_bound(val.begin() , val.end() , b[i]) - val.begin();
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    power[0] = 1;
    for(int i = 1; i < maxn; i++) power[i] = (power[i-1]*base)%mod;
    compress();

    int v_hsh = 0, check = 0;

    for(int i = 0; i < n; i++)
    {
        (v_hsh += power[n-i-1]) %= mod;
        (check += power[n-i-1]*(a[i+1])) %= mod;
    }

    vector <int> ans;

    for(int i = 1; i <= m; i++)
    {
        update(1 , 1 , m , b[i] , i , 1);

        if(i > n) update(1 , 1 , m , b[i-n] , 0 , 0);
        
        if(i >= n)
        {
            assert(st[1].cnt == n);

            if(st[1].hsh == check)
            {
                ans.push_back(i-n+1);
            }
            (check += v_hsh) %= mod;
        }
    }
    cout << ans.size() << '\n';
    for(int x: ans) cout << x << ' ';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 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