#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
struct pBIT {
vector<vector<pii>> tr;
pBIT (int sz) : tr(sz + 1, vector<pii>(1, make_pair(-1, 0))) {}
int get (int k, int ver) {
auto it = upper_bound(all(tr[k]), make_pair(ver, INT_MAX));
return prev(it)->second;
}
int p (int k) { return k & -k; }
void update (int k, int val, int ver) {
for (; k < tr.size(); k += p(k)) {
int cur = tr[k].back().second + val;
tr[k].push_back(make_pair(ver, cur));
}
}
int query (int k, int ver, int ans = 0) {
for (; k; k -= p(k)) ans += get(k, ver);
return ans;
}
};
struct BIT {
vector<int> tr;
BIT (int sz) : tr(sz + 1) {}
int p (int k) { return k & -k; }
void update (int k, int val) {
for (; k < tr.size(); k += p(k))
tr[k] += val;
}
int query (int k, int ans = 0) {
for (; k; k -= p(k)) ans += tr[k];
return ans;
}
};
vector<int> pFunc (vector<int> &vec, int sz) {
int n = vec.size();
vector<int> pi(n), pre(n);
pBIT tree(sz);
for (int i = 0; i < n; i++)
if (vec[i] < INT_MAX) tree.update(vec[i], 1, i);
BIT helper(sz);
for (int i = 0; i < n; i++) {
if (vec[i] == INT_MAX) continue;
helper.update(vec[i], 1); pre[i] = helper.query(vec[i]);
}
function<bool(int,int)> same = [&] (int i, int j) {
// [0..i-1] + i == [j-i..j-1] + j
if (vec[i] == INT_MAX || vec[j] == INT_MAX) return false;
return pre[i] == (pre[j] - tree.query(vec[j], j - i - 1));
};
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j && !same(j, i)) j = pi[j - 1];
if (same(j, i)) pi[i] = j + 1;
}
return pi;
}
map<int,int> mp;
void compress() {
int mark = 0;
for (pii it : mp) mp[it.first] = ++mark;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<int> s(n), h(m);
for (int i = 1; i <= n; i++) {
int p; cin >> p;
s[p - 1] = i;
}
for (int i = 0; i < m; i++) {
cin >> h[i];
mp[h[i]] = 0;
}
compress();
vector<int> vec = s;
vec.push_back(INT_MAX);
for (int u : h) vec.push_back(mp[u]);
vector<int> pi = pFunc(vec, max(n, m)), ans;
for (int i = 0; i < pi.size(); i++)
if (pi[i] == n) ans.push_back(i - 2 * n + 1);
cout << ans.size() << "\n";
for (int u : ans) cout << u << " ";
return 0;
}
Compilation message
mat.cpp: In member function 'void pBIT::update(int, int, int)':
mat.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (; k < tr.size(); k += p(k)) {
| ~~^~~~~~~~~~~
mat.cpp: In member function 'void BIT::update(int, int)':
mat.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (; k < tr.size(); k += p(k))
| ~~^~~~~~~~~~~
mat.cpp: In function 'int main()':
mat.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < pi.size(); i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
5080 KB |
Output is correct |
| 2 |
Correct |
20 ms |
4816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
5324 KB |
Output is correct |
| 2 |
Correct |
20 ms |
5080 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
47536 KB |
Output is correct |
| 2 |
Correct |
167 ms |
44776 KB |
Output is correct |
| 3 |
Correct |
462 ms |
55880 KB |
Output is correct |
| 4 |
Correct |
474 ms |
56304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
269 ms |
54040 KB |
Output is correct |
| 2 |
Correct |
409 ms |
49308 KB |
Output is correct |
| 3 |
Correct |
215 ms |
48484 KB |
Output is correct |
| 4 |
Correct |
205 ms |
46224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
250 ms |
52000 KB |
Output is correct |
| 2 |
Correct |
195 ms |
52416 KB |
Output is correct |
| 3 |
Correct |
262 ms |
49828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
534 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
518 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
492 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
531 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
