Submission #1151452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151452		adaawf	Matching (CEOI11_mat)	C++20	63 / 100	787 ms	31200 KiB

mat

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long int b = 1777013, bb, mod = 1e9 + 7, z = 0;
int a[1000005], f[1000005], lazy[2000005];
long long int power(long long int x, long long int y, long long int mod) {
    long long int res = 1, h = x;
    while (y) {
        if (y & 1) res = res * h % mod;
        h = h * h % mod;
        y >>= 1;
    }
    return res;
}
struct HASH {
    int x, c;
} t[2000005];
HASH Merge(HASH aa, HASH bb) {
    HASH res;
    res.x = aa.x + bb.x;
    if (res.x >= mod) res.x -= mod;
    res.c = aa.c + bb.c;
    return res;
}
void push(int v) {
    if (lazy[v] == 1) return;
    lazy[v << 1] = 1ll * lazy[v << 1] * lazy[v] % mod;
    lazy[v << 1 | 1] = 1ll * lazy[v << 1 | 1] * lazy[v] % mod;
    t[v << 1].x = 1ll * t[v << 1].x * lazy[v] % mod;
    t[v << 1 | 1].x = 1ll * t[v << 1 | 1].x * lazy[v] % mod;
    lazy[v] = 1;
}
void update(int v, int tl, int tr, int l, int r, long long int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[v].x = 1ll * t[v].x * x % mod;
        lazy[v] = 1ll * lazy[v] * x % mod;
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    update(v << 1, tl, mid, l, min(r, mid), x);
    update(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
void update2(int v, int tl, int tr, int x, int y) {
    if (tl == tr) {
        if (t[v].c == 0) {
            t[v] = {y, 1};
        }
        else t[v] = {0, 0};
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    if (mid >= x) update2(v << 1, tl, mid, x, y);
    else update2(v << 1 | 1, mid + 1, tr, x, y);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v].c;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    return sum(v << 1, tl, mid, l, min(r, mid)) + sum(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, m, c = 0, d = 0;
    cin >> n >> m;
    f[0] = 1;
    b = 1777013;
    for (int i = 1; i <= n; i++) {
        f[i] = 1ll * f[i - 1] * b % mod;
        int x;
        cin >> x;
        c += 1ll * x * f[i];
        d = (d + f[i]) % mod;
        c %= mod;
    }
    vector<int> v, vv;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        vv.push_back(a[i]);
    }
    bb = power(b, mod - 2, mod);
    sort(vv.begin(), vv.end());
    for (int i = 1; i <= n * 4; i++) lazy[i] = 1;
    for (int i = 1; i <= m; i++) {
        a[i] = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin() + 1;
        if (i > n) {
            update2(1, 1, m, a[i - n], 0);
            update(1, 1, m, a[i - n] + 1, m, bb);
        }
        int h = sum(1, 1, m, 1, a[i] - 1) + 1;
        update2(1, 1, m, a[i], 1ll * f[h] * i % mod);
        update(1, 1, m, a[i] + 1, m, b);
        if (i >= n && (t[1].x + mod - d * (i - n) % mod) % mod == c) {
            v.push_back(i - n + 1);
        }
    }
    cout << v.size() << '\n';
    for (int w : v) cout << w << " ";
}

• 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