#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tm (tl + tr) / 2
using ll = long long;
const int base = 137;
const int mxn = 1e6 + 7;
const int mod = 1e9 + 7;
long long pw[mxn], Hash;
int n, id[mxn];
int m, pl[mxn];
int val[mxn * 4];
int cnt[mxn * 4];
void upt(int id, int tl, int tr, int i, int x) {
if(tl == tr) {
if(x == 0)
val[id] = cnt[id] = 0;
else {
val[id] = x;
cnt[id] = 1;
}
return;
}
if(i <= tm) upt(id * 2 + 1, tl, tm, i, x);
else upt(id * 2 + 2, tm + 1, tr, i, x);
cnt[id] = cnt[id * 2 + 1] + cnt[id * 2 + 2];
val[id] = (val[id * 2 + 1] + val[id * 2 + 2] * pw[cnt[id * 2 + 1]] % mod) % mod;
}
ll fpow(ll a, int n) {
if(n == 0) return 1;
if(n == 1) return a;
int t = fpow(a * a % mod, n / 2);
if(n % 2 == 0) return t;
return t * a % mod;
}
ll inverse(ll a) {
return fpow(a, mod - 2);
}
signed main() {
pw[0] = 1;
for(int i = 1; i < mxn; i++)
pw[i] = pw[i - 1] * base % mod;
cin >> n >> m;
for(int i = 0; i < n; i++) {
int x; cin >> x;
int t = x * pw[i] % mod;
Hash = (Hash + t) % mod;
}
for(int i = 1; i <= m; i++) {
cin >> pl[i];
id[i] = i;
}
sort(id, id + m + 1, [&](int i, int j) { return pl[i] < pl[j]; });
for(int i = 0; i <= m; i++) pl[id[i]] = i;
for(int i = 0; i < n && i <= m; i++)
upt(0, 0, m, pl[i], i);
// for(int i = 0; i <= m; i++)
// cout << id[i] << ' ';
// cout << endl;
// for(int i = 0; i <= m; i++)
// cout << pl[i] << ' ';
// cout << endl;
const ll T = (pw[n] - 1) * inverse(base - 1) % mod;
// cout << "gay = " << val[0] << endl;
// cout << Hash << endl;
// cout << T << endl;
vector<int> ans;
for(int l = 1; l <= m; l++) {
int r = l + n - 1;
if(r > m) break;
// root-> upt_rem(pl[l - 1]);
// add(pl[r], r);
upt(0, 0, m, pl[l - 1], 0);
upt(0, 0, m, pl[r], r);
int Q = val[0];
int t = l - 1;
// cout << l << ' ' << r << ": " << Q << endl;
// cout << "t = " << t << endl;
t = t * T % mod;
t = (t + Hash) % mod;
// t = t * base % mod;
if(t == Q) ans.push_back(l);
}
cout << ans.size() << endl;
for(int i : ans) cout << i << ' ';
cout << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14428 KB |
Output is correct |
2 |
Correct |
8 ms |
14540 KB |
Output is correct |
3 |
Correct |
8 ms |
14680 KB |
Output is correct |
4 |
Correct |
7 ms |
14424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14428 KB |
Output is correct |
2 |
Correct |
8 ms |
14680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
16732 KB |
Output is correct |
2 |
Correct |
17 ms |
16732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
16888 KB |
Output is correct |
2 |
Correct |
19 ms |
16732 KB |
Output is correct |
3 |
Correct |
9 ms |
14428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
122 ms |
26140 KB |
Output is correct |
2 |
Correct |
131 ms |
25680 KB |
Output is correct |
3 |
Correct |
169 ms |
28500 KB |
Output is correct |
4 |
Correct |
192 ms |
28716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
27084 KB |
Output is correct |
2 |
Correct |
174 ms |
28092 KB |
Output is correct |
3 |
Correct |
147 ms |
26556 KB |
Output is correct |
4 |
Correct |
139 ms |
29024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
140 ms |
26752 KB |
Output is correct |
2 |
Correct |
132 ms |
24356 KB |
Output is correct |
3 |
Correct |
153 ms |
26244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
828 ms |
64460 KB |
Output is correct |
2 |
Correct |
1039 ms |
65536 KB |
Output is correct |
3 |
Correct |
876 ms |
65536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
752 ms |
63832 KB |
Output is correct |
2 |
Correct |
1002 ms |
64692 KB |
Output is correct |
3 |
Correct |
968 ms |
65536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
831 ms |
65536 KB |
Output is correct |
2 |
Runtime error |
664 ms |
65536 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
819 ms |
65536 KB |
Output is correct |
2 |
Correct |
856 ms |
65536 KB |
Output is correct |
3 |
Correct |
365 ms |
41580 KB |
Output is correct |
4 |
Correct |
778 ms |
65536 KB |
Output is correct |