oj.uz

Submission #922933

# Submission time Handle Problem Language Result Execution time Memory
922933 2024-02-06T10:03:22 Z dubabuba Matching (CEOI11_mat) C++14
0 / 100
 43 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

#define tm (tl + tr) / 2
#define int long long
using ll = long long;
const int base = 137;
const int mxn = 1e6 + 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 lazy, suma;
	ll valo;
	int power; // debug

	tree() {
		power = 0;
		// tl = tr = 0;
		lazy = valo = suma = 0;
	}
};


tree st[mxn * 4];
int find_sum(int id, int tl, int tr, int l, int r) {
	if(tl == l && r == tr) return st[id].suma;
	if(r <= tm) return find_sum(id * 2 + 1, tl, tm, l, r);
	if(tm < l) return find_sum(id * 2 + 2, tm + 1, tr, l, r);
	int L = find_sum(id * 2 + 1, tl, tm, l, tm);
	int R = find_sum(id * 2 + 2, tm + 1, tr, tm + 1, r);
	return L + R;
}

void pro(int id) {
	tree &self = st[id];
	tree &lc = st[id * 2 + 1];
	tree &rc = st[id * 2 + 2];

	if(self.lazy == 0) return;
	int d = abs(self.lazy);
	if(self.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.lazy += self.lazy;
	rc.lazy += self.lazy;
	self.lazy = 0;
}

void merge(int id) {
	tree &self = st[id];
	tree &lc = st[id * 2 + 1];
	tree &rc = st[id * 2 + 2];
	self.suma = lc.suma + rc.suma;
	self.valo = (lc.valo + rc.valo) % mod;
}

void upt_add(int id, int tl, int tr, int i, int x, int d) {
	tree &self = st[id];
	tree &rc = st[id * 2 + 2];

	if(tl == tr) {
		self.valo = x;
		self.suma = 1;
		return;
	}
	pro(id);
	if(i <= tm) {
		upt_add(id * 2 + 1, tl, tm, i, x, d);
		rc.lazy++;
		rc.valo = rc.valo * pw[1] % mod;
	}
	else upt_add(id * 2 + 2, tm + 1, tr, i, x, d);
	merge(id);
}

void upt_rem(int id, int tl, int tr, int i) {
	tree &self = st[id];
	tree &rc = st[id * 2 + 2];

	if(tl == tr) {
		self.valo = 0;
		self.suma = 0;
		return;
	}
	pro(id);
	if(i <= tm) {
		upt_rem(id * 2 + 1, tl, tm, i);
		rc.lazy--;
		rc.valo = rc.valo * in[1] % mod;
	}
	else upt_rem(id * 2 + 2, tm + 1, tr, i);
	merge(id);
}

int query(int id, int tl, int tr, int l, int r) {
	if(tl == l && r == tr) return st[id].valo;
	pro(id);
	if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
	if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);
	int L = query(id * 2 + 1, tl, tm, l, tm);
	int R = query(id * 2 + 2, tm + 1, tr, tm + 1, r);
	return (L + R) % mod;
}

void add(int id, int a) {
	// int d = root-> find_sum(0, id);
	int d = find_sum(0, 0, m, 0, id);
	// root-> upt_add(id, a * pw[d + 1] % mod, d + 1);
	upt_add(0, 0, m, 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();

	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]);
		upt_rem(0, 0, m, pl[l - 1]);
		add(pl[r], r);

		// ll Q = root-> query(0, m);
		ll Q = query(0, 0, m, 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
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 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 24 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 24 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 24 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 24 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 24 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 28 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -