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 <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <climits>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
ll mod = 1e9 + 7, p = 1000003, n, m, fen[1000001], fen2[1000001];
ll sum(ll *t, ll idx){
ll sum = 0;
while(idx > 0){
sum += t[idx];
sum %= mod;
idx -= idx&-idx;
}
return sum;
}
void add(ll *t, ll idx, ll val){
while(idx <= m){
t[idx] += val;
idx += idx&-idx;
}
}
int main(){
cin >> n >> m;
vector<ll> a(n), b(m);
for (ll i = 0; i < n; i++)
cin >> a[i];
for (ll i = 0; i < m; i++)
cin >> b[i];
vector<ll> c = a;
for (ll i = 0; i < n; i++)
a[c[i] - 1] = i + 1;
vector<ii> d;
for (ll i = 0; i < m; i++)
d.push_back({b[i], i});
sort(d.begin(), d.end());
for (ll i = 0; i < m; i++)
b[d[i].second] = i + 1;
ll hes = 0, hes2 = 0;
vector<ll> pows;
pows.push_back(1);
for (ll i = 1; i < m + 1; i++)
pows.push_back((pows[i - 1]*p)%mod);
for (ll i = 0; i < n; i++){
hes += pows[i]*a[i];
hes %= mod;
add(fen2, b[i], 1);
}
vector<ll> rj;
for (ll i = 0; i < n; i++){
add(fen, b[i], pows[i]);
hes2 += (sum(fen2, b[i])*pows[i])%mod;
hes2 %= mod;
}
if (hes == hes2)
rj.push_back(1);
for (ll i = n; i < m; i++){
hes *= p; hes %= mod;
hes2 -= sum(fen, m) - sum(fen, b[i - n]) + (sum(fen2, b[i - n])*pows[i - n])%mod;
while(hes2 < 0)
hes2 += mod;
add(fen2, b[i - n], -1);
add(fen, b[i - n], -sum(fen, b[i - n]) + sum(fen, b[i - n] - 1));
add(fen2, b[i], 1);
add(fen, b[i], pows[i]);
hes2 += sum(fen, m) - sum(fen, b[i]) + (sum(fen2, b[i])*pows[i])%mod;
while(hes2 < 0)
hes2 += mod;
hes2 %= mod;
if (hes == hes2)
rj.push_back(i - n + 2);
}
cout << rj.size() << endl;
for (ll i = 0; i < rj.size(); i++)
cout << rj[i] << " ";
return 0;
}
Compilation message (stderr)
mat.cpp: In function 'int main()':
mat.cpp:95:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (ll i = 0; i < rj.size(); i++)
| ~~^~~~~~~~~~~
# | 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... |