Submission #1267204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267204		canhnam357	Matching (CEOI11_mat)	C++20	100 / 100	876 ms	62212 KiB

mat

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
    f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
    f = (f < s ? f : s);
}
const int mod1 = 1035972859;
const int mod2 = 1704760909;
const int base = 1e6 + 5;
const int N = 1e6 + 5;
int p1[N], p2[N], inv1[N], inv2[N];
int power(long long a, int b, int mod)
{
    long long res = 1;
    while (b)
    {
        if (b & 1) (res *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}
struct fenwick
{
    int n;
    vector<long long> bit;
    fenwick() {}
    fenwick(int n)
    {
        this->n = n + 5;
        bit.resize(n + 5);
    }
    void add(int pos, long long val)
    {
        while (pos < n)
        {
            bit[pos] += val;
            pos += pos & -pos;
        }
    }
    long long get(int pos)
    {
        long long ans = 0;
        while (pos)
        {
            ans += bit[pos];
            pos -= pos & -pos;
        }
        return ans;
    }
    long long get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
};
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    p1[0] = p2[0] = 1;
    for (int i = 1; i < N; i++)
    {
        p1[i] = (1LL * p1[i - 1] * base) % mod1;
        p2[i] = (1LL * p2[i - 1] * base) % mod2;
    }
    inv1[N - 1] = power(p1[N - 1], mod1 - 2, mod1);
    inv2[N - 1] = power(p2[N - 1], mod2 - 2, mod2);
    for (int i = N - 2; i >= 0; i--)
    {
        inv1[i] = (1LL * inv1[i + 1] * base) % mod1;
        inv2[i] = (1LL * inv2[i + 1] * base) % mod2;
    }
    int k, n;
    cin >> k >> n;
    vector<int> zzz(k), a(k);
    for (int &i : zzz) cin >> i, i--;
    for (int i = 0; i < k; i++)
    {
        a[zzz[i]] = i + 1;
    }
    {   
        auto cc = a;
        sort(all(cc));
        cc.erase(unique(all(cc)), cc.end());
        for (int &i : a) i = upper_bound(all(cc), i) - cc.begin();
    }
    pair<long long, long long> hashed;
    {
        int h1 = 0, h2 = 0;
        for (int j = 0; j < k; j++)
        {
            int x = a[j];
            h1 = (h1 + 1LL * x * p1[j]) % mod1;
            h2 = (h2 + 1LL * x * p2[j]) % mod2;
            //cout << h1 << ' ' << h2 << ' ' << h3 << '\n';
        }
        hashed = {h1, h2};
    }
    vector<int> v(n);
    for (int &i : v) cin >> i;
    auto cc = v;
    sort(all(cc));
    cc.erase(unique(all(cc)), cc.end());
    for (int &i : v) i = upper_bound(all(cc), i) - cc.begin();
    fenwick tree1(n), tree2(n);
    fenwick tree(n);
    vector<int> has(n + 5);
    long long H1 = 0, H2 = 0;
    vector<int> ans;
    for (int i = 0; i < n; i++)
    {
        int p = tree.get(v[i] - 1);
        if (!has[v[i]]) 
        {
            tree.add(v[i], 1);
            (H1 += tree1.get(v[i] + 1, n)) %= mod1;
            (H2 += tree2.get(v[i] + 1, n)) %= mod2;
        }
        (H1 += (p + 1LL) * p1[i]) %= mod1;
        (H2 += (p + 1LL) * p2[i]) %= mod2;
        has[v[i]]++;
        //tree1.update(v[i] + 1, n, base);
        //tree2.update(v[i] + 1, n, base);
        tree1.add(v[i], p1[i]);
        tree2.add(v[i], p2[i]);
        //cout << H1 << ' ' << H2 << '\n';
        //cout << H1 << ' ' << H2 << ' ' << H3 << '\n';
        if (i >= k - 1)
        {
            if (make_pair((H1 * inv1[i - k + 1]) % mod1, (H2 * inv2[i - k + 1]) % mod2) == hashed)
            {
                ans.push_back(i - k + 2);
            }
            int j = i - k + 1;
            p = tree.get(v[j] - 1);
            H1 = ((H1 - (p + 1LL) * p1[j]) % mod1 + mod1) % mod1;
            H2 = ((H2 - (p + 1LL) * p2[j]) % mod2 + mod2) % mod2;
            //tree1.update(v[j] + 1, n, inv1[1]);
            //tree2.update(v[j] + 1, n, inv2[1]);
            has[v[j]]--;
            tree1.add(v[j], -p1[j]);
            tree2.add(v[j], -p2[j]);
            if (!has[v[j]]) 
            {
                H1 = (H1 - tree1.get(v[j] + 1LL, n) % mod1 + mod1) % mod1;
                H2 = (H2 - tree2.get(v[j] + 1LL, n) % mod2 + mod2) % mod2;
                tree.add(v[j], -1);
            }
            //cout << "- ";
            //cout << (H1 * inv1[i - k + 1]) % mod1 << ' ' << (H2 * inv2[i - k + 1]) % mod2 << '\n';
        }
    }
    cout << ans.size() << '\n';
    for (int 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