This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int fast_power(int n, int m){
int res = 1;
while (m){
if (m % 2)
res = 1ll * res * n % mod;
n = 1ll * n * n % mod;
m >>= 1;
}
return res;
}
const int BASE = MAXN;
const int INV_BASE = fast_power(BASE, mod - 2);
struct BIT {
int t[MAXN];
void add(int p, int v){
for (p += 5; p < MAXN; p += p & -p){
t[p] += v;
}
}
int get(int p){
int res = 0;
for (p += 5; p; p -= p & -p){
res += t[p];
}
return res;
}
} bit;
const int off = (1<<20);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
int t[off << 1], lazy[off << 1];
void init(){
for (int i = 0; i < off * 2; i++) lazy[i] = 1;
}
int unit = 0;
void pull(int idx){
t[idx] = (t[ls] + t[rs]) % mod;
}
void update(int idx, int u){
t[idx+=off] = u;
while (idx/=2)
pull(idx);
}
void push(int idx){
if (lazy[idx] == 1) return;
t[idx] = 1ll * t[idx] * lazy[idx] % mod;
if (idx < off){
lazy[ls] = 1ll * lazy[ls] * lazy[idx] % mod;
lazy[rs] = 1ll * lazy[rs] * lazy[idx] % mod;
}
lazy[idx] = 1;
}
int get(int l, int r, int idx=1, int lo=0, int hi=off){
push(idx);
if (r <= lo || hi <= l)
return unit;
if (l <= lo && hi <= r)
return t[idx];
int mi = (lo+hi)>>1;
return (get(l, r, ls, lo, mi) + get(l, r, rs, mi, hi)) % mod;
}
void mul_update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
push(idx);
if (r <= lo || hi <= l)
return ;
if (l <= lo && hi <= r){
lazy[idx] = 1ll * lazy[idx] * val;
push(idx);
return ;
}
int mi = (lo+hi)>>1;
mul_update(l, r, val, ls, lo, mi);
mul_update(l, r, val, rs, mi, hi);
pull(idx);
}
void add_update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
push(idx);
if (r <= lo || hi <= l)
return ;
if (l <= lo && hi <= r){
t[idx] = val;
return ;
}
int mi = (lo+hi)>>1;
add_update(l, r, val, ls, lo, mi);
add_update(l, r, val, rs, mi, hi);
pull(idx);
}
} seg;
int a[MAXN], b[MAXN];
int powers[MAXN];
int m, n;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
seg.init();
cin >> m >> n;
for (int i = 1; i <= m; i++){
cin >> b[i];
}
vector<int> deco(n);
for (int i = 1; i <= n; i++){
cin >> a[i];
deco[i - 1] = a[i];
}
sort(all(deco));
for (int i = 1; i <= n; i++){
a[i] = lower_bound(all(deco), a[i]) - deco.begin() + 1;
}
int perm_hash = 0;
int sum = 0;
powers[0] = 1;
for (int i = 1; i <= m; i++){
powers[i] = 1ll * powers[i - 1] * BASE % mod;
perm_hash += 1ll * b[i] * powers[i] % mod;
sum += powers[i];
if (sum >= mod) sum -= mod;
if (perm_hash >= mod) perm_hash -= mod;
}
for (int i = 1; i < m; i++){
bit.add(a[i], 1);
}
for (int i = 1; i < m; i++){
seg.add_update(a[i], a[i] + 1, 1ll * powers[bit.get(a[i])] * i % mod);
}
vector<int> ans;
for (int i = 1; i + m - 1 <= n; i++){
int r = i + m - 1;
bit.add(a[r], 1);
// insert number r at postion a[r] with power bit.get(a[r]) and increase every power after it
seg.add_update(a[r], a[r] + 1, 1ll * powers[bit.get(a[r])] * r % mod);
seg.mul_update(a[r] + 1, off, BASE);
if (seg.get(0, off) == perm_hash){
ans.pb(i);
}
seg.add_update(a[i], a[i] + 1, 0);
seg.mul_update(a[i] + 1, off, INV_BASE);
bit.add(a[i], -1);
perm_hash += sum;
if (perm_hash >= mod) perm_hash -= mod;
}
cout << sz(ans) << endl;
for (auto x : ans) cout << x << ' ';
}
# | 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... |