Submission #922914

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
922914	2024-02-06T09:19:12 Z	dubabuba	Matching (CEOI11_mat)	C++14	36 / 100	193 ms	65536 KB

#include <bits/stdc++.h>
using namespace std;

#define int long long
using ll = long long;
const int base = 137;
const int mxn = 2e6 + 7;
const ll mod = 1e9 + 7;
int m, a[mxn], id[mxn];
int n, p[mxn], pl[mxn];
long long in[mxn], pw[mxn];

ll fpow(ll a, int n) {
	if(n == 0) return 1;
	if(n == 1) return a;
	int t = fpow(a * a % mod, n / 2);
	if(n % 2 == 0) return t;
	return t * a % mod;
}

ll inverse(ll a) {
	return fpow(a, mod - 2);
}

void init() {
	sort(id, id + m + 1, [&] (int i, int j) {
		return a[i] < a[j];
	});

	pw[0] = in[0] = 1;
	pw[1] = base;
	in[1] = inverse(base);
	for(int i = 1; i < mxn; i++) {
		pw[i] = pw[i - 1] * pw[1] % mod;
		in[i] = in[i - 1] * in[1] % mod;
	}
}

struct tree {
	int tl, tr;
	int lazy, suma;
	ll valo;
	int power; // debug
	tree *lc, *rc;

	tree() {
		power = 0;
		tl = tr = 0;
		lazy = valo = suma = 0;
		lc = rc = NULL;
	}

	tree(int l, int r) {
		power = 0;
		tl = l, tr = r;
		lazy = suma = valo = 0;
		lc = rc = NULL;
	}

	void build() {
		if(tl == tr) return;
		int tm = (tl + tr) / 2;
		lc = new tree(tl, tm);
		rc = new tree(tm + 1, tr);
		lc-> build();
		rc-> build();
	}

	int find_sum(int l, int r) {
		int tm = (tl + tr) / 2;
		if(tl == l && r == tr) return suma;
		if(r <= tm) return lc-> find_sum(l, r);
		if(tm < l) return rc-> find_sum(l, r);
		int L = lc-> find_sum(l, tm);
		int R = rc-> find_sum(tm + 1, r);
		return L + R;
	}

	void pro() {
		if(lazy == 0) return;
		int d = abs(lazy);
		if(lazy < 0) {
			lc-> valo = lc-> valo * in[d] % mod;
			rc-> valo = rc-> valo * in[d] % mod;
		}
		else {
			lc-> valo = lc-> valo * pw[d] % mod;
			rc-> valo = rc-> valo * pw[d] % mod;
		}
		lc-> power += lazy;
		rc-> power += lazy;
		lc-> lazy += lazy;
		rc-> lazy += lazy;
		lazy = 0;
	}

	void merge() {
		suma = lc-> suma + rc-> suma;
		valo = (lc-> valo + rc-> valo) % mod;
	}

	void upt_add(int i, int x, int d) {
		if(tl == tr) {
			power = d;
			valo = x;
			suma = 1;
			return;
		}
		pro();
		int tm = (tl + tr) / 2;
		if(i <= tm) {
			lc-> upt_add(i, x, d);
			rc-> lazy++;
			rc-> power++;
			rc-> valo = rc-> valo * pw[1] % mod;
		}
		else rc-> upt_add(i, x, d);
		merge();
	}

	void upt_rem(int i) {
		if(tl == tr) {
			valo = 0;
			suma = 0;
			return;
		}
		pro();
		int tm = (tl + tr) / 2;
		if(i <= tm) {
			lc-> upt_rem(i);
			rc-> lazy--;
			rc-> power--;
			rc-> valo = rc-> valo * in[1] % mod;
		}
		else rc-> upt_rem(i);
		merge();
	}

	int query(int l, int r) {
		if(tl == l && r == tr) return valo;
		int tm = (tl + tr) / 2; pro();
		if(r <= tm) return lc-> query(l, r);
		if(tm < l) return rc-> query(l, r);
		int L = lc-> query(l, tm);
		int R = rc-> query(tm + 1, r);
		return (L + R) % mod;
	}

	// void log() {
	// 	// pro();
	// 	if(tl == tr) {
	// 		if(valo != 0)
	// 		cout << tl << ": " << power << ' ' << valo << endl;
	// 		return;
	// 	}
	// 	pro();
	// 	lc-> log();
	// 	rc-> log();
	// }
} *root;

void add(int id, int a) {
	int d = root-> find_sum(0, id);
	root-> upt_add(id, a * pw[d + 1] % mod, d + 1);
}

signed main() {
	cin.tie(0)-> sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> p[i];
		// p[i]--;
	}
	for(int i = 1; i <= m; i++) {
		cin >> a[i];
		id[i] = i;
	}

	init();
	root = new tree(0, m);
	root-> build();

	for(int i = 0; i <= m; i++)
		pl[id[i]] = i;

	for(int i = 0; i < n && i <= m; i++)
		add(pl[i], i);

	ll K = 0;
	for(int i = 0; i < n; i++) {
		ll t = p[i] * pw[i] % mod;
		K = (K + t) % mod;
	}
	const ll T = (pw[n] - 1) * inverse(base - 1) % mod;

	vector<int> ans;
	for(int l = 1; l <= m; l++) {
		int r = l + n - 1;
		if(r > m) break;
		root-> upt_rem(pl[l - 1]);
		add(pl[r], r);

		ll Q = root-> query(0, m);
		ll t = l - 1;
		t = t * T % mod;
		t = (t + K) % mod;
		t = t * base % mod;

		if(t == Q) ans.push_back(l);	}

	cout << ans.size() << endl;
	for(int i : ans) cout << i << ' ';
	cout << endl;
	return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	39516 KB	Output is correct
2	Correct	14 ms	39512 KB	Output is correct
3	Correct	14 ms	39516 KB	Output is correct
4	Correct	16 ms	39516 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	39772 KB	Output is correct
2	Correct	14 ms	39572 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	42588 KB	Output is correct
2	Correct	25 ms	42332 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	42588 KB	Output is correct
2	Correct	26 ms	42660 KB	Output is correct
3	Correct	16 ms	40028 KB	Output is correct

Subtask #5
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	54 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	59 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	55 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	193 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	193 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	169 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	174 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #922914

Compilation message