Submission #739187

#	Time	Username	Problem	Language	Result	Execution time	Memory
739187		GrindMachine	Matching (CEOI11_mat)	C++17	100 / 100	1213 ms	58176 KiB

mat

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

how to check if subarray of len n is good?
create an array with pairs (a[i],i)
sort the array

array is good if the order of indices in the sorted array is same as the required order

find if every subarray of len n is good or not

checking for equality of 2 arrays => gives intuition for hashing

we can find target hash (hash of the given order of indices)

we want to support following ops:
add guy
del guy
find hash of current array

use segtree to do this
put index i into the a[i]th pos in the segtree (0 if doesnt exist)
hash of whole array can be computed by efficiently merging left and right children

also, when we compute the hash of the subarray starting at i, all hash values will be shifted by (i-1)
take this also into account

*/

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> ps = {5791, 8237, 3067, 6991, 3527};
vector<int> mods = {791139137, 433567597, 271149607, 561259969, 222708581};
ll pows[N][2];

void precalc() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    shuffle(all(ps), rng);
    shuffle(all(mods), rng);

    rep(j, 2) {
        pows[0][j] = 1;
        rep1(i, N - 1) {
            pows[i][j] = pows[i - 1][j] * ps[j] % mods[j];
        }
    }
}

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        array<int, 2> a;
        int cnt;

        data() {
            a.fill(0);
            cnt = 0;
        }
    };

    data neutral = data();

    data merge(data &left, data &right) {
        data curr;

        rep(j, 2) {
            curr.a[j] = (left.a[j] + right.a[j] * pows[left.cnt][j]) % mods[j];
        }

        curr.cnt = left.cnt + right.cnt;

        return curr;
    }

    void create(int i, T v) {
        rep(j, 2) {
            tr[i].a[j] = (v * ps[j]) % mods[j];
        }

        tr[i].cnt = (v > 0);
    }

    void modify(int i, T v) {
        rep(j, 2) {
            tr[i].a[j] = (v * ps[j]) % mods[j];
        }

        tr[i].cnt = (v > 0);
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    precalc();
    int n, m; cin >> n >> m;
    vector<int> p(n + 5), a(m + 5);
    rep1(i, n) cin >> p[i];
    rep1(i, m) cin >> a[i];

    vector<int> b;
    rep1(i, m) b.pb(a[i]);

    sort(all(b));
    b.resize(unique(all(b)) - b.begin());

    rep1(i, m) {
        a[i] = lower_bound(all(b), a[i]) - b.begin();
    }

    array<int, 2> want, toadd;
    want.fill(0), toadd.fill(0);

    rep1(i, n) {
        rep(j, 2) {
            want[j] = (want[j] + pows[i][j] * p[i]) % mods[j];
            toadd[j] = (toadd[j] + pows[i][j]) % mods[j];
        }
    }

    segtree<int> st(m + 5);
    rep1(i, n) {
        st.pupd(a[i], i);
    }

    vector<int> ans;

    if (st.query(0, m - 1).a == want) {
        ans.pb(1);
    }

    for (int i = 2; i <= m - n + 1; ++i) {
        rep(j, 2) {
            want[j] = (want[j] + toadd[j]) % mods[j];
        }

        st.pupd(a[i - 1], 0);
        st.pupd(a[i + n - 1], i + n - 1);

        if (st.query(0, m - 1).a == want) {
            ans.pb(i);
        }
    }

    cout << sz(ans) << endl;
    trav(x, ans) cout << x << " ";
    cout << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(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