#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
const int INF = (int)2e9;
template<class T, class F = function<T(const T&, const T&)>>
struct Fenwick {
int n;
T def;
F f;
vector<T> tree;
Fenwick(int n_, T def_, F f_) : n(n_), def(def_), f(f_), tree(n + 1, def) {}
inline int lsb(int x) {
return x & -x;
}
void Update(int pos, T val) {
for (++pos; pos <= n; pos += lsb(pos)) {
tree[pos] = f(tree[pos], val);
}
}
T Query(int pos) {
T ret = def;
for (++pos; pos; pos -= lsb(pos)) {
ret = f(ret, tree[pos]);
}
return ret;
}
};
void GetSmallBig(const vector<int> &p, vector<int> &small, vector<int> &big) {
int n = p.size();
Fenwick<pair<int, int>> mn(n, {-1, -1}, [](pair<int, int> a, pair<int, int> b) {
return max(a, b);
});
Fenwick<pair<int, int>> mx(n, {INF, -1}, [](pair<int, int> a, pair<int, int> b) {
return min(a, b);
});
for (int i = 0; i < n; ++i) {
small[i] = mn.Query(p[i]).second;
big[i] = mx.Query(n - p[i] - 1).second;
mn.Update(p[i], make_pair(p[i], i));
mx.Update(n - p[i] - 1, make_pair(p[i], i));
}
}
bool Match(int k, int i, const vector<int> &p,
const vector<int> &small, const vector<int> &big) {
bool ret = true;
ret &= big[k] == -1 || p[i] < p[i - k + big[k]];
ret &= small[k] == -1 || p[i] > p[i - k + small[k]];
return ret;
}
void GetPi(const vector<int> &p, vector<int> &pi,
const vector<int> &small, const vector<int> &big) {
pi[0] = 0;
int k = 0;
for (int i = 1; i < (int)p.size(); ++i) {
while (k != 0 && !Match(k, i, p, small, big)) k = pi[k - 1];
if (Match(k, i, p, small, big)) ++k;
pi[i] = k;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<int> p(n);
for (int i = 0; i < n; ++i) {
int s; cin >> s; --s;
p[s] = i;
}
vector<int> small(n, -1), big(n, -1), pi(n);
GetSmallBig(p, small, big);
GetPi(p, pi, small, big);
vector<int> text(m);
for (int i = 0; i < m; ++i) {
cin >> text[i];
}
vector<int> ans;
int k = 0;
for (int i = 0; i < m; ++i) {
while (k != 0 && !Match(k, i, text, small, big)) k = pi[k - 1];
if (Match(k, i, text, small, big)) ++k;
if (k == n) {
ans.emplace_back(i - n + 1);
k = pi[k - 1];
}
}
cout << ans.size() << endl;
for (int &x : ans) {
cout << 1 + x << ' ';
}
cout << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
632 KB |
Output is correct |
2 |
Correct |
6 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
632 KB |
Output is correct |
2 |
Correct |
6 ms |
632 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
1792 KB |
Output is correct |
2 |
Correct |
27 ms |
1500 KB |
Output is correct |
3 |
Correct |
58 ms |
2228 KB |
Output is correct |
4 |
Correct |
58 ms |
2120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
2404 KB |
Output is correct |
2 |
Correct |
34 ms |
1632 KB |
Output is correct |
3 |
Correct |
41 ms |
2108 KB |
Output is correct |
4 |
Correct |
43 ms |
3696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
2660 KB |
Output is correct |
2 |
Correct |
44 ms |
2096 KB |
Output is correct |
3 |
Correct |
43 ms |
1904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
8920 KB |
Output is correct |
2 |
Correct |
1002 ms |
31964 KB |
Output is correct |
3 |
Correct |
132 ms |
4116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
308 ms |
10360 KB |
Output is correct |
2 |
Correct |
133 ms |
4564 KB |
Output is correct |
3 |
Correct |
964 ms |
30312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
165 ms |
6504 KB |
Output is correct |
2 |
Correct |
216 ms |
15212 KB |
Output is correct |
3 |
Correct |
199 ms |
5652 KB |
Output is correct |
4 |
Correct |
650 ms |
31856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
188 ms |
7484 KB |
Output is correct |
2 |
Correct |
188 ms |
5776 KB |
Output is correct |
3 |
Correct |
112 ms |
4048 KB |
Output is correct |
4 |
Correct |
677 ms |
28760 KB |
Output is correct |