제출 #347354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347354		jesus_coconut	Matching (CEOI11_mat)	C++17	63 / 100	2096 ms	65540 KiB

mat

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;

int const MOD = 1e9 + 7;
ll const baza = 997;

ll potf(ll n, int k) {
    ll ret = 1;
    while (k) {
        if (k % 2) {
            ret *= n;
            ret %= MOD;
        }
        n *= n;
        n %= MOD;
        k /= 2;
    }
    return ret;
}

template<class T>
struct BIT{
	vector<T> bit;

	explicit BIT(int N) : bit(N, 0) {}

	void add(int pos, T val) {
		for (; pos < (int) bit.size(); pos += pos & -pos) {
			bit[pos] += val;
		    bit[pos] %= MOD;
		}
	}

	T sum(int r) {
		T res{};
		for (; r > 0; r -= r & -r) {
			res += bit[r];
			res %= MOD;
		}
		return res;
	}

	T sum(int l, int r) {
	    T ret = sum(r) - sum(l - 1);
	    ret %= MOD;
	    if (ret < 0) ret += MOD;
	    return ret;
	}
};

ll divmod(ll a, ll b) {
    return (a * potf(b, MOD - 2)) % MOD;
}

vector<int> v, p;

vector<ll> potinv, potreg;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    potinv.resize(m + 10);
    potreg.resize(m + 10);
    potreg[0] = 1;
    for (int i = 1; i < m + 10; ++i) {
        potreg[i] = (potreg[i - 1] * baza) % MOD;
    }
    potinv[0] = 1;
    ll divtmp = divmod(1, baza);
    for (int i = 1; i < m + 10; ++i) {
        potinv[i] = (potinv[i - 1] * divtmp) % MOD;
    }
    p.resize(n);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        --a;
        p[a] = i + 1;
    }
    v.resize(m);
    for (auto &a : v) cin >> a;
    vector<int> tmp = v;
    sort(begin(tmp), end(tmp));
    tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));
    for (auto &a : v) {
        a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
    }

    BIT<ll> bit(m + 10);
    ll pot = 1;
    for (int i = m - 1; i > m - n; --i) {
        bit.add(v[i], pot);
        pot *= baza;
        pot %= MOD;
    }
    vector<ll> nxt(m + 10), prv(m + 10);
    int divi = 0;
    for (int i = m - n; i >= 0; --i) {
        nxt[i] = (bit.sum(v[i] + 1, m + 9) * potinv[divi]) % MOD;
        bit.add(v[i + n - 1], -potreg[divi]);
        bit.add(v[i], pot);
        pot *= baza;
        pot %= MOD;
        divi++;
        prv[i + n - 1] = (bit.sum(v[i + n - 1] + 1, m + 9) * potinv[divi]) % MOD;
    }
    ll fh = 0;
    for (auto a : p) {
        fh *= baza;
        fh += a;
        fh %= MOD;
    }
    ll h = 0;
    vector<int> fix(n);
    for (int i = 0; i < n; ++i) {
        fix[i] = v[i];
    }
    tmp = fix;
    sort(begin(tmp), end(tmp));
    tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));

    for (auto &a : fix) {
        a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
    }

    vector<int> ord(m), ordb(m);
    oset<int> s;
    for (int i = m - 1; i > m - n; --i) {
        s.insert(v[i]);
    }
    for (int i = m - n; i >= 0; --i) {
        ord[i] = s.order_of_key(v[i]) + 1;
        s.insert(v[i]);
        s.erase(v[i + n - 1]);
    }
    s.clear();
    for (int i = 0; i < n - 1; ++i) {
        s.insert(v[i]);
    }
    for (int i = n - 1; i < m; ++i) {
        ordb[i] = s.order_of_key(v[i]) + 1;
        s.insert(v[i]);
        s.erase(v[i - n + 1]);
    }

    for (int i = 0; i < n; ++i) {
        h *= baza;
        h += fix[i];
        h %= MOD;
    }
    vector<int> ans;
    ans.reserve(n / 2);
    if (fh == h) ans.push_back(0);
    ll rem = potf(baza, n - 1);
    for (int i = n; i < m; ++i) {
        h -= rem * ord[i - n];
        h %= MOD;
        h -= nxt[i - n];
        h %= MOD;
        h += prv[i];
        h %= MOD;
        if (h < 0) h += MOD;
        h *= baza;
        h += ordb[i];
        h %= MOD;
        if (h < 0) h += MOD;
        if (fh == h) {
            ans.push_back(i - n + 1);
        }
    }
    cout << ans.size() << '\n';
    for (auto a : ans) cout << a + 1 << ' ';

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