#include<bits/stdc++.h>
#define breturn return
#define ll long long
using namespace std;
const ll b = 31337;
const ll mod = 1e9 + 7;
int n, m,bn, arr[1000001], a, pb[20000001], che[1000001], chash, rhash, tour[40000001], bre, act[40000001], cnt;
vector<pair<int, int> > perm;
vector<int> odg;
vector<int> v;
ll mul(ll x, ll y) {
breturn (x * y)%mod;
}
ll ad(ll x, ll y) {
if(x + y >= mod) breturn x + y - mod;
else if(x + y < 0) breturn x + y + mod;
breturn x + y;
}
ll quer(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) {
if(l > bx or r < ax) breturn 0;
if(l >= ax and r <= bx) breturn tour[x];
ll mid = (l + r)/2;
breturn ad(quer(ax, bx, x * 2, l, mid), quer(ax, bx, x * 2 + 1, mid + 1, r));
}
ll smol(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) {
if(l > bx or r < ax) breturn 0;
if(l >= ax and r <= bx) breturn act[x];
ll mid = (l + r)/2;
breturn smol(ax, bx, x * 2, l, mid) + smol(ax, bx, x * 2 + 1, mid + 1, r);
}
ll bp(ll p, ll x) {
if(x == 0) breturn 1;
if(x%2) breturn mul(bp(p, x - 1), p);
ll xx = bp(p, x/2);
breturn mul(xx, xx);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
bn = (1 << ((int)log2(m - 1) + 1));
pb[0] = 1;
for(int i = 0; i < n; i++) {
cin >> a;
arr[a - 1] = i + 1;
}
for(int i = 1; i < bn; i++) pb[i] = mul(pb[i - 1], b);
for(int i = 0; i < n; i++) {
chash = mul(chash, b);
chash = ad(chash, arr[i]);
}
for(int i = 0; i < m; i++) {
cin >> arr[i];
v.push_back(arr[i]);
}
sort(v.begin(), v.end());
for(int i = 0; i < n; i++) perm.push_back({arr[i], i});
sort(perm.begin(), perm.end());
for(int i = 0; i < n; i++) che[perm[i].second] = i + 1;
for(int i = 0; i < n; i++) {
rhash = mul(rhash, b);
rhash = ad(rhash, che[i]);
int x = lower_bound(v.begin(), v.end(), arr[i]) - v.begin() + 1;
tour[x + bn] = pb[n - i - 1];
act[x + bn] = 1;
}
for(int i = bn - 1; i > 0; i--) tour[i] = ad(tour[i * 2], tour[i * 2 +1]), act[i] = act[i * 2] + act[i * 2 + 1];
if(rhash == chash) odg.push_back(1);
for(int i = n; i < m; i++) {
int x = lower_bound(v.begin(), v.end(), arr[i - n]) - v.begin() + 1;
rhash = ad(rhash, -mul(smol(0, x), pb[n - 1]));
rhash = ad(rhash, -mul(quer(x + 1, bn - 1), pb[cnt]));
x += bn;
act[x] = 0;
tour[x] = 0;
x /= 2;
while(x) act[x] = act[x * 2] + act[x * 2 + 1], tour[x] = ad(tour[x * 2], tour[x * 2 + 1]), x /= 2;
x = lower_bound(v.begin(), v.end(), arr[i]) - v.begin() + 1;
rhash = ad(rhash, mul(quer(x + 1, bn - 1), pb[cnt]));
cnt ++;
rhash = mul(rhash, b);
rhash = ad(rhash, smol(0, x) + 1);
x += bn;
act[x] = 1;
tour[x] = bp(pb[cnt], mod - 2);
x /= 2;
while(x) act[x] = act[x * 2] + act[x * 2 + 1], tour[x] = ad(tour[x * 2], tour[x * 2 + 1]), x /= 2;
if(rhash == chash) odg.push_back(i - n + 2);
}
cout << odg.size() << '\n';
for(int i = 0; i < odg.size(); i++) cout << odg[i] << " ";
}
Compilation message
mat.cpp: In function 'int main()':
mat.cpp:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = 0; i < odg.size(); i++) cout << odg[i] << " ";
| ~~^~~~~~~~~~~~
| # |
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 |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1260 KB |
Output is correct |
| 3 |
Correct |
4 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
7292 KB |
Output is correct |
| 2 |
Correct |
311 ms |
6760 KB |
Output is correct |
| 3 |
Correct |
411 ms |
7656 KB |
Output is correct |
| 4 |
Correct |
389 ms |
7656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
295 ms |
7784 KB |
Output is correct |
| 2 |
Correct |
468 ms |
6760 KB |
Output is correct |
| 3 |
Correct |
314 ms |
7144 KB |
Output is correct |
| 4 |
Correct |
299 ms |
8944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
287 ms |
7868 KB |
Output is correct |
| 2 |
Correct |
273 ms |
7656 KB |
Output is correct |
| 3 |
Correct |
349 ms |
7272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1744 ms |
33500 KB |
Output is correct |
| 2 |
Correct |
715 ms |
56528 KB |
Output is correct |
| 3 |
Correct |
1905 ms |
33244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1482 ms |
31592 KB |
Output is correct |
| 2 |
Execution timed out |
2065 ms |
28508 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1963 ms |
30476 KB |
Output is correct |
| 2 |
Correct |
1599 ms |
46312 KB |
Output is correct |
| 3 |
Execution timed out |
2087 ms |
39788 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1816 ms |
31452 KB |
Output is correct |
| 2 |
Execution timed out |
2085 ms |
40268 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
