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>
#define ll long long
#define fi first
#define se second
#define maxi(a, base) a = max(a, base)
#define mize(a, base) a = min(a, base)
#define getbaseit(a, i) ((a) >> (i) & 1)
#define FOR(i, a, base) for(int i=a, _n=base; i<=_n; ++i)
#define FORD(i, a, base) for(int i=a, _n=base; i>=_n; --i)
#define REP(i, _n) for(int i=0; i<_n; ++i)
#define sz(a) ((int)(a).size())
#define all(a) a.baseegin(), a.end()
#define pbase push_baseack
#define mp make_pair
#define ii pair<int, int>
using namespace std;
typedef long long hash_type;
const int DIM = 2e5+5;
const hash_type MOD1 = 1e9+7;
const hash_type MOD2 = 1e9+7;
const int base=1e4;
struct segment_tree{
int hash1,hash2;
int cnt;
} aint[DIM*4];
pair <int,int> v[DIM];
int nrm[DIM];
int p1[DIM],p2[DIM];
vector <int> sol;
int n,m,i,j,x;
void update (int nod, int st, int dr, int poz, int val){
if (st == dr){
aint[nod].hash1 = aint[nod].hash2 = val;
if (val)
aint[nod].cnt = 1;
else aint[nod].cnt = 0;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[nod].hash1 = (1LL * aint[fiu_st].hash1 * p1[ aint[fiu_dr].cnt ] % MOD1 + aint[fiu_dr].hash1) % MOD1;
aint[nod].hash2 = (1LL * aint[fiu_st].hash2 * p2[ aint[fiu_dr].cnt ] % MOD2 + aint[fiu_dr].hash2) % MOD2;
aint[nod].cnt = aint[fiu_st].cnt + aint[fiu_dr].cnt;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>m>>n;
int hash1 = 0, hash2 = 0;
for (i=1;i<=m;i++){
cin>>x;
hash1 = (1LL * hash1 * base % MOD1 + x) % MOD1;
hash2 = (1LL * hash2 * base % MOD2 + x) % MOD2;
}
p1[0] = p2[0] = 1;
for (i=1;i<=n;i++){
p1[i] = 1LL * p1[i-1] * base % MOD1;
p2[i] = 1LL * p2[i-1] * base
% MOD2;
}
for (i=1;i<=n;i++){
cin>>v[i].first;
v[i].second = i;
}
sort (v+1,v+n+1);
for (i=1;i<=n;i++)
nrm[v[i].second] = i;
for (i=1;i<m;i++)
update (1,1,n,nrm[i],i);
int sum1 = 0, sum2 = 0;
for (i=0;i<m;i++){
sum1 = (sum1 + p1[i]) % MOD1;
sum2 = (sum2 + p2[i]) % MOD2;
}
for (i=m;i<=n;i++){
/// adaug elem asta
update (1,1,n,nrm[i],i);
int val1 = (aint[1].hash1 - 1LL * sum1 * (i-m) % MOD1 + MOD1) % MOD1;
int val2 = (aint[1].hash2 - 1LL * sum2 * (i-m) % MOD2 + MOD2) % MOD2;
if (val1 == hash1)
sol.push_back(i-m+1);
/// sterg i-m+1
update (1,1,n,nrm[i-m+1],0);
}
cout<<sol.size()<<"\n";
for (auto it : sol)
cout<<it<<" ";
return 0;
}
//Jelly1010
Compilation message (stderr)
mat.cpp: In function 'int main()':
mat.cpp:106:13: warning: unused variable 'val2' [-Wunused-variable]
106 | int val2 = (aint[1].hash2 - 1LL * sum2 * (i-m) % MOD2 + MOD2) % MOD2;
| ^~~~
# | 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... |