oj.uz

답안 #922965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922965 2024-02-06T11:14:45 Z dubabuba Matching (CEOI11_mat) C++14
100 / 100
 891 ms 57860 KB 
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define tm (tl + tr) / 2
using ll = long long;

#pragma GCC optimize("O3")

const int base = 137;
const int mxn = 1e6 + 7;
const int mod = 1e9 + 7;
long long pw[mxn], Hash;
int n, id[mxn];
int m, pl[mxn];

ll val[mxn * 4];
int cnt[mxn * 4];

void upt(int id, int tl, int tr, int i, int x) {
	if(tl == tr) {
		if(x == 0)
			val[id] = cnt[id] = 0;
		else {
			val[id] = x;
			cnt[id] = 1;
		}
		return;
	}

	if(i <= tm) upt(id * 2 + 1, tl, tm, i, x);
	else upt(id * 2 + 2, tm + 1, tr, i, x);
	cnt[id] = cnt[id * 2 + 1] + cnt[id * 2 + 2];
	val[id] = (val[id * 2 + 1] + val[id * 2 + 2] * pw[cnt[id * 2 + 1]] % mod) % mod;
}

ll fpow(ll a, int n) {
	if(n == 0) return 1;
	if(n == 1) return a;
	ll 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);
}

signed main() {
	cin.tie(0)-> sync_with_stdio(0);

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

	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		int x; cin >> x;
		int t = x * pw[i] % mod;
		Hash = (Hash + t) % mod;
	}

	for(int i = 1; i <= m; i++) {
		cin >> pl[i];
		id[i] = i;
	}

	sort(id, id + m + 1, [&](int i, int j) { return pl[i] < pl[j]; });
	for(int i = 0; i <= m; i++) pl[id[i]] = i;

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

	// for(int i = 0; i <= m; i++)
	// 	cout << id[i] << ' ';
	// cout << endl;
	// for(int i = 0; i <= m; i++)
	// 	cout << pl[i] << ' ';
	// cout << endl;

	const ll T = (pw[n] - 1) * inverse(base - 1) % mod;
	// cout << "gay = " << val[0] << endl;
	// cout << Hash << endl;
	// cout << T << endl;

	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);
		upt(0, 0, m, pl[l - 1], 0);
		upt(0, 0, m, pl[r], r);
		ll Q = val[0];
		ll t = l - 1;
		// cout << l << ' ' << r << ": " << Q << endl;
		// cout << "t = " << t << endl;
		t = T * t % mod;
		t = (t + Hash) % 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15708 KB Output is correct
2 Correct 7 ms 15692 KB Output is correct
3 Correct 7 ms 15708 KB Output is correct
4 Correct 7 ms 15708 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15704 KB Output is correct
2 Correct 8 ms 15704 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 18012 KB Output is correct
2 Correct 15 ms 18012 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 18012 KB Output is correct
2 Correct 15 ms 18020 KB Output is correct
3 Correct 8 ms 15664 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 26960 KB Output is correct
2 Correct 106 ms 26192 KB Output is correct
3 Correct 146 ms 27728 KB Output is correct
4 Correct 142 ms 27728 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 27476 KB Output is correct
2 Correct 137 ms 27476 KB Output is correct
3 Correct 117 ms 27884 KB Output is correct
4 Correct 115 ms 28392 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 26724 KB Output is correct
2 Correct 103 ms 26196 KB Output is correct
3 Correct 118 ms 27476 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 631 ms 50644 KB Output is correct
2 Correct 729 ms 52896 KB Output is correct
3 Correct 739 ms 48736 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 581 ms 50732 KB Output is correct
2 Correct 891 ms 48172 KB Output is correct
3 Correct 692 ms 51540 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 686 ms 50084 KB Output is correct
2 Correct 629 ms 57860 KB Output is correct
3 Correct 793 ms 49716 KB Output is correct
4 Correct 437 ms 50768 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 635 ms 50572 KB Output is correct
2 Correct 673 ms 50316 KB Output is correct
3 Correct 286 ms 33608 KB Output is correct
4 Correct 509 ms 52308 KB Output is correct