#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int a[maxn], b[maxn], h[maxn];
int fen[maxn];
int f[maxn];
int get(int idx){
int ret = 0;
for (; idx; idx -= idx & -idx)
ret += fen[idx];
return ret;
}
void add(int idx, int val){
for (; idx < maxn; idx += idx & -idx)
fen[idx] += val;
}
int main(){
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
int x;
cin >> x;
a[x - 1] = i;
}
vector<int> cmp;
for (int i = 0; i < m; i++){
cin >> h[i];
cmp.push_back(h[i]);
}
sort(cmp.begin(), cmp.end());
for (int i = 0; i < m; i++)
h[i] = lower_bound(cmp.begin(), cmp.end(), h[i]) - cmp.begin() + 1;
for (int i = 0; i < n; i++){
add(a[i], +1);
b[i] = get(a[i]);
}
for (int i = 0; i < n; i++)
add(a[i], -1); // vitex
f[0] = f[1] = 0;
int k = 0;
for (int i = 1; i < n; i++){
add(a[i], +1);
int now = get(a[i]);
while (k > 0 and b[k] != now){
for (int t = i - k; t < i - f[k]; t++)
add(a[t], -1);
k = f[k];
now = get(a[i]);
}
k += (b[k] == now);
f[i + 1] = k;
}
memset(fen, 0, sizeof fen);
vector<int> ans;
k = 0;
for (int i = 0; i < m; i++){
add(h[i], +1);
int now = get(h[i]);
while (k > 0 and b[k] != now){
for (int t = i - k; t < i - f[k]; t++)
add(h[t], -1);
k = f[k];
now = get(h[i]);
}
k += (b[k] == now);
if (k == n){
ans.push_back(i - k + 1);
for (int t = i - k + 1; t < i - f[k] + 1; t++)
add(h[t], -1);
k = f[k];
}
}
cout << ans.size() << '\n';
for (auto it : ans)
cout << it + 1 << " ";
cout << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
4216 KB |
Output is correct |
2 |
Correct |
7 ms |
4216 KB |
Output is correct |
3 |
Correct |
7 ms |
4216 KB |
Output is correct |
4 |
Correct |
7 ms |
4292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
4344 KB |
Output is correct |
2 |
Correct |
8 ms |
4344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
4732 KB |
Output is correct |
2 |
Correct |
15 ms |
4728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4856 KB |
Output is correct |
2 |
Correct |
15 ms |
4728 KB |
Output is correct |
3 |
Correct |
8 ms |
4344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
6640 KB |
Output is correct |
2 |
Correct |
67 ms |
6252 KB |
Output is correct |
3 |
Correct |
118 ms |
6896 KB |
Output is correct |
4 |
Correct |
119 ms |
6892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
90 ms |
7152 KB |
Output is correct |
2 |
Correct |
106 ms |
6252 KB |
Output is correct |
3 |
Correct |
83 ms |
6768 KB |
Output is correct |
4 |
Correct |
89 ms |
8304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
7276 KB |
Output is correct |
2 |
Correct |
79 ms |
6768 KB |
Output is correct |
3 |
Correct |
93 ms |
6644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
478 ms |
25820 KB |
Output is correct |
2 |
Correct |
926 ms |
40436 KB |
Output is correct |
3 |
Correct |
369 ms |
18524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
476 ms |
25696 KB |
Output is correct |
2 |
Correct |
539 ms |
19036 KB |
Output is correct |
3 |
Correct |
855 ms |
36572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
414 ms |
22108 KB |
Output is correct |
2 |
Correct |
364 ms |
29788 KB |
Output is correct |
3 |
Correct |
476 ms |
22880 KB |
Output is correct |
4 |
Correct |
584 ms |
38496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
414 ms |
23136 KB |
Output is correct |
2 |
Correct |
494 ms |
23300 KB |
Output is correct |
3 |
Correct |
192 ms |
13672 KB |
Output is correct |
4 |
Correct |
634 ms |
37860 KB |
Output is correct |