Submission #1267203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267203		canhnam357	Matching (CEOI11_mat)	C++20	63 / 100	679 ms	106892 KiB

mat

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
const int mod1 = 1035972859;
const int mod2 = 1704760909;
const int mod3 = 2143922441;
const int base = 1e6 + 5;
const int N = 1e6 + 5;
int p1[N], p2[N], p3[N], inv1[N], inv2[N], inv3[N];
int power(int a, int b, int mod)
{
	int res = 1;
	while (b)
	{
		if (b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return res;
}
struct fenwick
{
	int n;
	vector<int> bit;
	fenwick() {}
	fenwick(int n)
	{
		this->n = n + 5;
		bit.resize(n + 5);
	}
	void add(int pos, int val)
	{
		while (pos < n)
		{
			bit[pos] += val;
			pos += pos & -pos;
		}
	}
	int get(int pos)
	{
		int ans = 0;
		while (pos)
		{
			ans += bit[pos];
			pos -= pos & -pos;
		}
		return ans;
	}
	int get(int l, int r)
	{
		return get(r) - get(l - 1);
	}
	int find(int k)
	{
		int sum = 0, pos = 0;
		for (int i = __lg(n); i >= 0; i--)
		{
			if (pos + (1 << i) < n && sum + bit[pos + (1 << i)] < k)
			{
				sum += bit[pos + (1 << i)];
				pos += (1 << i);
			}
		}
		return pos + 1;
	}
};
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	p1[0] = p2[0] = p3[0] = 1;
	for (int i = 1; i < N; i++)
	{
		p1[i] = (p1[i - 1] * base) % mod1;
		p2[i] = (p2[i - 1] * base) % mod2;
		p3[i] = (p3[i - 1] * base) % mod3;
	}
	inv1[N - 1] = power(p1[N - 1], mod1 - 2, mod1);
	inv2[N - 1] = power(p2[N - 1], mod2 - 2, mod2);
	inv3[N - 1] = power(p3[N - 1], mod3 - 2, mod3);
	for (int i = N - 2; i >= 0; i--)
	{
		inv1[i] = (inv1[i + 1] * base) % mod1;
		inv2[i] = (inv2[i + 1] * base) % mod2;
		inv3[i] = (inv3[i + 1] * base) % mod3;
	}
	int k, n;
	cin >> k >> n;
	vector<int> zzz(k), a(k);
	for (int &i : zzz) cin >> i, i--;
	for (int i = 0; i < k; i++)
	{
		a[zzz[i]] = i + 1;
	}
	{	
		auto cc = a;
		sort(all(cc));
		cc.erase(unique(all(cc)), cc.end());
		for (int &i : a) i = upper_bound(all(cc), i) - cc.begin();
	}
	tuple<int, int, int> hashed;
	{
		int h1 = 0, h2 = 0, h3 = 0;
		for (int j = 0; j < k; j++)
		{
			int x = a[j];
			h1 = (h1 + x * p1[j]) % mod1;
			h2 = (h2 + x * p2[j]) % mod2;
			h3 = (h3 + x * p3[j]) % mod3;
			//cout << h1 << ' ' << h2 << ' ' << h3 << '\n';
		}
		hashed = {h1, h2, h3};
	}
	vector<int> v(n);
	for (int &i : v) cin >> i;
	auto cc = v;
	sort(all(cc));
	cc.erase(unique(all(cc)), cc.end());
	for (int &i : v) i = upper_bound(all(cc), i) - cc.begin();
	fenwick tree1(n), tree2(n), tree3(n);
	fenwick tree(n);
	vector<int> has(n + 5);
	int H1 = 0, H2 = 0, H3 = 0;
	vector<int> ans;
	for (int i = 0; i < n; i++)
	{
		int p = tree.get(v[i] - 1);
		if (!has[v[i]]) 
		{
			tree.add(v[i], 1);
			(H1 += tree1.get(v[i] + 1, n)) %= mod1;
			(H2 += tree2.get(v[i] + 1, n)) %= mod2;
			(H3 += tree3.get(v[i] + 1, n)) %= mod3;
		}
		(H1 += (p + 1) * p1[i]) %= mod1;
		(H2 += (p + 1) * p2[i]) %= mod2;
		(H3 += (p + 1) * p3[i]) %= mod3;
		has[v[i]]++;
		//tree1.update(v[i] + 1, n, base);
		//tree2.update(v[i] + 1, n, base);
		tree1.add(v[i], p1[i]);
		tree2.add(v[i], p2[i]);
		tree3.add(v[i], p3[i]);
		//cout << H1 << ' ' << H2 << '\n';
		//cout << H1 << ' ' << H2 << ' ' << H3 << '\n';
		if (i >= k - 1)
		{
			if (make_tuple((H1 * inv1[i - k + 1]) % mod1, (H2 * inv2[i - k + 1]) % mod2, (H3 * inv3[i - k + 1]) % mod3) == hashed)
			{
				ans.push_back(i - k + 2);
			}
			int j = i - k + 1;
			p = tree.get(v[j] - 1);
			H1 = ((H1 - (p + 1) * p1[j]) % mod1 + mod1) % mod1;
			H2 = ((H2 - (p + 1) * p2[j]) % mod2 + mod2) % mod2;
			H3 = ((H3 - (p + 1) * p3[j]) % mod3 + mod3) % mod3;
			//tree1.update(v[j] + 1, n, inv1[1]);
			//tree2.update(v[j] + 1, n, inv2[1]);
			has[v[j]]--;
			tree1.add(v[j], -p1[j]);
			tree2.add(v[j], -p2[j]);
			tree3.add(v[j], -p3[j]);
			if (!has[v[j]]) 
			{
				H1 = (H1 - tree1.get(v[j] + 1, n) % mod1 + mod1) % mod1;
				H2 = (H2 - tree2.get(v[j] + 1, n) % mod2 + mod2) % mod2;
				H3 = (H3 - tree3.get(v[j] + 1, n) % mod3 + mod3) % mod3;
				tree.add(v[j], -1);
			}
			//cout << "- ";
			//cout << (H1 * inv1[i - k + 1]) % mod1 << ' ' << (H2 * inv2[i - k + 1]) % mod2 << '\n';
		}
	}
	cout << ans.size() << '\n';
	for (int i : ans) cout << 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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10