#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
int const MOD = 1e9 + 7;
ll const baza = 997;
ll potf(ll n, int k) {
ll ret = 1;
while (k) {
if (k % 2) {
ret *= n;
ret %= MOD;
}
n *= n;
n %= MOD;
k /= 2;
}
return ret;
}
template<class T>
struct BIT{
vector<T> bit;
explicit BIT(int N) : bit(N, 0) {}
void add(int pos, T val) {
for (; pos < (int) bit.size(); pos += pos & -pos) {
bit[pos] += val;
bit[pos] %= MOD;
}
}
T sum(int r) {
T res{};
for (; r > 0; r -= r & -r) {
res += bit[r];
res %= MOD;
}
return res;
}
T sum(int l, int r) {
T ret = sum(r) - sum(l - 1);
ret %= MOD;
if (ret < 0) ret += MOD;
return ret;
}
};
ll divmod(ll a, ll b) {
return (a * potf(b, MOD - 2)) % MOD;
}
vector<int> v;
vector<ll> potinv, potreg, nxt, prv;
vector<int> ans, ord, ordb;
BIT<ll> bit(1);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
potinv.resize(m + 10);
potreg.resize(m + 10);
potreg[0] = 1;
for (int i = 1; i < m + 10; ++i) {
potreg[i] = (potreg[i - 1] * baza) % MOD;
}
potinv[0] = 1;
ll divtmp = divmod(1, baza);
for (int i = 1; i < m + 10; ++i) {
potinv[i] = (potinv[i - 1] * divtmp) % MOD;
}
ll fh = 0;
{
vector<int> p(n);
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
--a;
p[a] = i + 1;
}
fh = 0;
for (auto a : p) {
fh *= baza;
fh += a;
fh %= MOD;
}
}
v.resize(m);
for (auto &a : v) cin >> a;
vector<int> tmp = v;
sort(begin(tmp), end(tmp));
tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));
for (auto &a : v) {
a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
}
bit.bit.resize(m + 10, 0);
ll pot = 1;
for (int i = m - 1; i > m - n; --i) {
bit.add(v[i], pot);
pot *= baza;
pot %= MOD;
}
nxt.resize(m + 10), prv.resize(m + 10);
int divi = 0;
for (int i = m - n; i >= 0; --i) {
nxt[i] = (bit.sum(v[i] + 1, m + 9) * potinv[divi]) % MOD;
bit.add(v[i + n - 1], -potreg[divi]);
bit.add(v[i], pot);
pot *= baza;
pot %= MOD;
divi++;
prv[i + n - 1] = (bit.sum(v[i + n - 1] + 1, m + 9) * potinv[divi]) % MOD;
}
ll h = 0;
{
vector<int> fix(n);
for (int i = 0; i < n; ++i) {
fix[i] = v[i];
}
tmp = fix;
sort(begin(tmp), end(tmp));
tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));
for (auto &a : fix) {
a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
}
for (int i = 0; i < n; ++i) {
h *= baza;
h += fix[i];
h %= MOD;
}
}
tmp.clear();
ord.resize(m), ordb.resize(m);
bit.bit.assign(m + 10, 0);
for (int i = m - 1; i > m - n; --i) {
bit.add(v[i], 1);
}
for (int i = m - n; i >= 0; --i) {
ord[i] = bit.sum(v[i]) + 1;
bit.add(v[i], 1);
bit.add(v[i + n - 1], -1);
}
bit.bit.assign(m + 10, 0);
for (int i = 0; i < n - 1; ++i) {
bit.add(v[i], 1);
}
for (int i = n - 1; i < m; ++i) {
ordb[i] = bit.sum(v[i]) + 1;
bit.add(v[i], 1);
bit.add(v[i - n + 1], -1);
}
v.clear();
ans.reserve(n / 2);
if (fh == h) ans.push_back(0);
ll rem = potreg[n - 1];
for (int i = n; i < m; ++i) {
h -= rem * ord[i - n];
h %= MOD;
h -= nxt[i - n];
h %= MOD;
h += prv[i];
h %= MOD;
if (h < 0) h += MOD;
h *= baza;
h += ordb[i];
h %= MOD;
if (h < 0) h += MOD;
if (fh == h) {
ans.push_back(i - n + 1);
}
}
cout << ans.size() << '\n';
for (auto a : ans) cout << a + 1 << ' ';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
10316 KB |
Output is correct |
| 2 |
Correct |
139 ms |
10860 KB |
Output is correct |
| 3 |
Correct |
184 ms |
11560 KB |
Output is correct |
| 4 |
Correct |
182 ms |
11688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
11700 KB |
Output is correct |
| 2 |
Correct |
189 ms |
11500 KB |
Output is correct |
| 3 |
Correct |
143 ms |
11372 KB |
Output is correct |
| 4 |
Correct |
144 ms |
13540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
11692 KB |
Output is correct |
| 2 |
Correct |
128 ms |
11320 KB |
Output is correct |
| 3 |
Correct |
171 ms |
11332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
931 ms |
56660 KB |
Output is correct |
| 2 |
Correct |
1305 ms |
65536 KB |
Output is correct |
| 3 |
Correct |
890 ms |
50540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
861 ms |
53788 KB |
Output is correct |
| 2 |
Correct |
1404 ms |
61956 KB |
Output is correct |
| 3 |
Correct |
1296 ms |
65536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
926 ms |
56212 KB |
Output is correct |
| 2 |
Correct |
778 ms |
65536 KB |
Output is correct |
| 3 |
Correct |
1118 ms |
54068 KB |
Output is correct |
| 4 |
Correct |
605 ms |
65536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
776 ms |
56544 KB |
Output is correct |
| 2 |
Correct |
1018 ms |
55636 KB |
Output is correct |
| 3 |
Correct |
345 ms |
32316 KB |
Output is correct |
| 4 |
Correct |
782 ms |
65536 KB |
Output is correct |
