#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define He_he_boy ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ld long double
#define pb push_back
#define pf push_front
#define eb emplace_back
#define fi first
#define se second
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define mx_e max_element
#define open freopen("fcolor.in", "r", stdin);
#define close freopen("fcolor.out", "w", stdout);
#define endl cout << '\n'
#define run(a) for (ll w23 = 1; w23 <= a; w23++)
typedef int ll;
using namespace std;
const ld eps = 0.00001, Pi = 3.14159275358979323846;
const ll mod = 1e9 + 7;
ll mod2 = 11, tt;
/// --------------------------------------------------------
ll n, m;
ll a[1000010];
ll b[1000010], p[1000010];
ll T[4000010], Sz[4000010];
void up(ll x, ll l, ll r, ll j, ll v){
if(l > j or r < j) return;
if(l == r){
T[x] = v;
Sz[x] = (v > 0);
return;
}
ll m = (l + r) / 2;
up(x * 2, l, m, j, v);
up(x * 2 + 1, m + 1, r, j, v);
ll k = Sz[2 * x];
T[x] = T[x + x] + (p[k] * T[2 * x + 1]) % mod;T[x] %= mod;
Sz[x] = k + Sz[2 * x + 1];
}
void Ali() {
cin >> n >> m;
for(ll i = 1;i <= n;i ++){
cin >> a[i];
}
for(ll i = 1;i <= m;i ++){
cin >> b[i];
}
ll ans = 1;
for(ll i = 1;i < n;i ++){
ans = (ans + p[i]) % mod;
}
vector<pair<ll, ll>>v;
for(ll i = 1;i <= m;i ++){
v.pb({b[i], i});
}
sort(all(v));
for(ll i = 0 ;i < m;i ++){
b[v[i].se] = i + 1;
}
ll Hs = 0;
for(ll i = 1;i <= n;i ++){
Hs = (Hs + (a[i] * p[i - 1]) % mod) % mod;
}
vector<ll>ot;
for(ll j = 1;j <= m;j ++){
up(1, 1, m, b[j], j);
if(Sz[1] >= n){
if(Sz[1] > n){
up(1, 1, m, b[j - n], 0);
Hs = (Hs + ans) % mod;
}
if(T[1] == Hs){
ot.pb(j - n + 1);
}
}
}
cout << ot.size() << '\n';
for(auto to : ot){
cout << to << ' ';
}
cout << '\n';
}
/// --------------------------------------------------------
int main() {
// open
// close;
// He_he_boy;
ll gg = 1; tt = 0;p[0] = 1;
for(ll i = 1;i <= 1e6 + 2;i ++){
p[i] = (p[i - 1] * mod2) % mod;
}
// cin >> gg;
while (gg--) {
Ali();
// cout << '\n';
}
/*
**PLUS ULTRA**
*/
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |