Submission #772293

#	Time	Username	Problem	Language	Result	Execution time	Memory
772293		NK_	Matching (CEOI11_mat)	C++17	0 / 100	586 ms	65536 KiB

mat

	// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back

using ll = long long;
template<class T> using V = vector<T>;


const int MOD1 = 1e9+7;
const int MOD2 = 998244353;
const ll base = 1009;

const int nax = 1e6+6;

V<ll> POW1, POW2;

struct T {
	ll H1, H2; int len;

	bool operator==(T a) {
		return a.H1 == H1 && a.H2 == H2;
	};	
};

T comb(T a, T b) { 
	T c = a; c.len += b.len;
	c.H1 = ((a.H1 * POW1[b.len]) + b.H1) % MOD1;
	c.H2 = ((a.H2 * POW2[b.len]) + b.H2) % MOD2;
	return c;
}

struct Seg {
	const T ID = {0, 0, 0}; 

	int N; V<T> seg;
	void init(int n) {
		N = 1; while(N < n) N *= 2;
		seg.assign(2*N, ID);
	}

	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }

	void upd(int p, T v, int x = 1, int L = 0, int R = -1) {
		if (R == -1) R = N - 1;
		if (L == R) {
			seg[x] = v; return;
		}

		int M = (L + R) / 2;
		if (p <= M) upd(p, v, 2*x, L, M);
		else upd(p, v, 2*x+1, M+1, R);
		pull(x);
	}

	T qry(int l, int r, int x = 1, int L = 0, int R = -1) {
		if (R == -1) R = N - 1;	
		if (r < L || R < l) return ID;
		if (l <= L && R <= r) return seg[x];

		int M = (L + R) / 2;
		return comb(qry(l, r, 2*x, L, M), qry(l, r, 2*x+1, M+1, R));
	}

	T get() { return seg[1]; }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	POW1 = POW2 = {1};
	for(int t = 0; t < nax; t++) {
		POW1.pb((POW1.back() * base) % MOD1);
		POW2.pb((POW2.back() * base) % MOD2);
	}

	int N, M; cin >> N >> M;

	V<int> A(N); for(auto& x : A) { cin >> x; --x; }
	V<int> B(M); for(auto& x : B) cin >> x;

	int K = -1;
	{
		map<int, int> mp; int cur = 0;
		for(auto& x : B) mp[x]++;
		for(auto& p : mp) p.second = cur++;
		for(auto& x : B) x = mp[x];
		K = cur;
	}

	for(auto& x : B) cout << x << " ";
	cout << endl;

	Seg st; st.init(K);

	auto print = [&]() {
		for(int i = 0; i < K; i++) {
			T res = st.qry(i, i);
			cout << i << " -> " << res.H1 << " " << res.H2 << " " << res.len << endl;
		}
	};

	T H = {0, 0, 0}, R = {0, 0, 0}, REM = {0, 0, 0}; 

	for(int i = 0; i < N; i++) {
		H = comb(H, {A[i] + 1, A[i] + 1, 1});
		R = comb(R, {1, 1, 1});
	}

	V<int> ans;
	for(int i = 0; i < N; i++) st.upd(B[i], {i + 1, i + 1, 1});
	// for(int i = 1; i <= N; i++) st.upd(B[i], {i + 1 - 1, i + 1 - 1, 1});


	// print();

	// cout << "H -> " << H.H1 << " " << H.H2 << " " << H.len << endl;
	// cout << "R -> " << R.H1 << " " << R.H2 << " " << R.len << endl;

	auto check = [&](int i) {
		T res = st.get(); 

		// REMOVE REMOVE
		if ((res.H1 -= REM.H1) < 0) res.H1 += MOD1;
		if ((res.H2 -= REM.H2) < 0) res.H2 += MOD2;

		// cout << "REM -> " << REM.H1 << " " << REM.H2 << " " << REM.len << endl;
		// cout << i << " -> " << res.H1 << " " << res.H2 << " " << res.len << endl;
		// cout << endl;
		if (res == H) ans.push_back(i);
	};

	check(0);

	for(int i = N; i < M; i++) {
		// ADD R
		if ((REM.H1 += R.H1) >= MOD1) REM.H1 -= MOD1;
		if ((REM.H2 += R.H2) >= MOD2) REM.H2 -= MOD2;

		// ADD i
		st.upd(B[i], {i + 1, i + 1, 1});

		// REMOVE i - N
		st.upd(B[i - N], {0, 0, 0});

		// print();

		check(i - N + 1);
	}

	cout << size(ans) << nl;
	for(auto& x : ans) cout << x+1 << " ";
	cout << nl;

    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:100:7: warning: variable 'print' set but not used [-Wunused-but-set-variable]
  100 |  auto print = [&]() {
      |       ^~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10