Submission #1169273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169273		htphong0909	Matching (CEOI11_mat)	C++20	100 / 100	698 ms	49016 KiB

mat

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

int priceS[1101001];
int priceT[1101001];
int comp[1101001];
int kmp[1101001];

int bit[1101001];
int bitTemp[1101001];
int nbit;

void update(int u, const int val, const bool t) {
    u += 2;
    if (!t) for (; u <= nbit; u += u & -u) bitTemp[u] += val;
    else for (; u <= nbit; u += u & -u) bit[u] += val;
}

int get(int u, const bool t) {
    u += 2;
    int res = 0;
    if (!t) for (; u > 0; u -= u & -u) res += bitTemp[u];
    else for (; u > 0; u -= u & -u) res += bit[u];
    return res;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        priceS[x] = i;
    }
    priceS[n + 1] = priceS[n];
    kmp[0] = -1;
    kmp[1] = 0;
    nbit = n + 2;

    for (int i = 2, curLen = 0; i <= n; i++) {
        while ((curLen > -1 && get(priceS[curLen + 1], false) != get(priceS[i], true)) || curLen == n) {
            for (int j = curLen; j > kmp[curLen]; j--) {
                update(priceS[j], -1, false);
                update(priceS[i - j], -1, true);
            }
            curLen = kmp[curLen];
        }
        kmp[i] = ++curLen;
        update(priceS[curLen], 1, false);
        update(priceS[i], 1, true);
    }

    memset(bitTemp, 0, sizeof(bitTemp));
    memset(bit, 0, sizeof(bit));
    nbit = m + 2;

    for (int i = 1; i <= m; i++) {
        cin >> priceT[i];
        comp[i] = priceT[i];
    }
    sort(comp + 1, comp + m + 1);
    for (int i = 1; i <= m; i++) {
        priceT[i] = lower_bound(comp + 1, comp + m + 1, priceT[i]) - comp;
    }

    vector<int> ans;
    for (int i = 1, curLen = 0; i <= m; i++) {
        while ((curLen > -1 && get(priceS[curLen + 1], false) != get(priceT[i], true)) || curLen == n) {
            for (int j = curLen; j > kmp[curLen]; j--) {
                update(priceS[j], -1, false);
                update(priceT[i - j], -1, true);
            }
            curLen = kmp[curLen];
        }
        if (++curLen == n) ans.push_back(i - n + 1);
        update(priceS[curLen], 1, false);
        update(priceT[i], 1, true);

    }
    cout << ans.size() << '\n';
    for (const int p : ans) cout << p << " ";
    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