Submission #1178211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178211		duongquanghai08	Matching (CEOI11_mat)	C++20	63 / 100	132 ms	8124 KiB

mat

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 5;
const int base = 5e4 + 4;
const int MOD = 1e9 + 7;
int n, m;
int a[N], b[N], pw[N];
pii ST[4 * N];
void update(int id, int l, int r, int pos, int val) {
    if(pos < l || pos > r) return;
    if(l == r) {
        if(val == 0) ST[id] = {0, 0};
        else ST[id] = {val, 1};
        return;
    }
    int mid = (l + r) / 2;
    update(id * 2, l, mid, pos, val);
    update(id * 2 + 1, mid + 1, r, pos, val);
    ST[id].fi = (1LL * ST[id * 2].fi * pw[ST[id * 2 + 1].se] + ST[id * 2 + 1].fi) % MOD;
    ST[id].se = ST[id * 2].se + ST[id * 2 + 1].se;
}
void Solve() {
    cin >> n >> m;
    int Hash = 0, nxt = 0;
    pw[0] = 1;
    for(int i = 1; i <= n; i++) pw[i] = (1LL * pw[i - 1] * base) % MOD;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        Hash = (1LL * Hash * base + x) % MOD;
        nxt = (nxt + pw[i - 1]) % MOD;
    }
    for(int i = 1; i <= m; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + m + 1);
    for(int i = 1; i <= m; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    for(int i = 1; i <= n; i++) update(1, 1, m, a[i], i);
    vector<int> ans;
    for(int i = n; i <= m; i++) {
        if(Hash == ST[1].fi) ans.push_back(i - n + 1);
        update(1, 1, m, a[i - n + 1], 0);
        update(1, 1, m, a[i + 1], i + 1);
        Hash = (Hash + nxt) % MOD;
    }
    cout << ans.size() << '\n';
    for(auto x : ans) cout << x << ' ';

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
}

• 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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10