oj.uz

답안 #739187

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739187 2023-05-10T06:57:45 Z GrindMachine Matching (CEOI11_mat) C++17
100 / 100
 1213 ms 58176 KB 
// 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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 15956 KB Output is correct
2 Correct 20 ms 15972 KB Output is correct
3 Correct 20 ms 15956 KB Output is correct
4 Correct 19 ms 15976 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 15956 KB Output is correct
2 Correct 21 ms 15968 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 16716 KB Output is correct
2 Correct 33 ms 16576 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 16688 KB Output is correct
2 Correct 34 ms 16724 KB Output is correct
3 Correct 22 ms 15956 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 21912 KB Output is correct
2 Correct 188 ms 22112 KB Output is correct
3 Correct 243 ms 22568 KB Output is correct
4 Correct 238 ms 22468 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 22748 KB Output is correct
2 Correct 257 ms 22484 KB Output is correct
3 Correct 188 ms 22480 KB Output is correct
4 Correct 166 ms 24424 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 22892 KB Output is correct
2 Correct 180 ms 22452 KB Output is correct
3 Correct 202 ms 22348 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1006 ms 49012 KB Output is correct
2 Correct 896 ms 51408 KB Output is correct
3 Correct 1048 ms 40432 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 916 ms 47064 KB Output is correct
2 Correct 1151 ms 47448 KB Output is correct
3 Correct 919 ms 51144 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1081 ms 48776 KB Output is correct
2 Correct 864 ms 58176 KB Output is correct
3 Correct 1213 ms 46896 KB Output is correct
4 Correct 592 ms 51260 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1008 ms 49216 KB Output is correct
2 Correct 1092 ms 47700 KB Output is correct
3 Correct 456 ms 32192 KB Output is correct
4 Correct 706 ms 50880 KB Output is correct