#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 BIT {
vector<int> tr;
BIT (int sz) : tr(sz + 1, INT_MIN) {}
int p (int k) { return k & -k; }
void update (int k, int val) {
for (; k < tr.size(); k += p(k)) tr[k] = max(tr[k], val);
}
int query (int k, int ans = INT_MIN) {
for (; k; k -= p(k)) ans = max(ans, tr[k]);
return ans;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<int> pos(n + 1), s(n), h(m);
for (int i = 1; i <= n; i++) {
cin >> pos[i];
s[--pos[i]] = i;
}
for (int i = 0; i < m; i++) cin >> h[i];
s.push_back(INT_MAX);
for (int u : h) s.push_back(u);
vector<int> lower(n), upper(n), pi(n + m + 1), ans;
BIT lw(n + 1), up(n + 1);
for (int i = 0; i < n; i++) {
int lb = lw.query(s[i]), ub = up.query(n - s[i] + 1);
lower[i] = (lb == INT_MIN ? -1 : i - pos[lb]);
upper[i] = (ub == INT_MIN ? -1 : i - pos[-ub]);
lw.update(s[i], s[i]);
up.update(n - s[i] + 1, -s[i]);
}
function<bool(int,int)> ok = [&] (int j, int i) {
if (max(s[j], s[i]) == INT_MAX) return 0;
if (lower[j] != -1)
if (s[i - lower[j]] > s[i]) return 0;
if (upper[j] != -1)
if (s[i - upper[j]] < s[i]) return 0;
return 1;
};
for (int i = 1; i < n + m + 1; i++) {
int j = pi[i - 1];
while (j && !ok(j, i)) j = pi[j - 1];
if (ok(j, i)) pi[i] = j + 1;
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 BIT::update(int, int)':
mat.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (; k < tr.size(); k += p(k)) tr[k] = max(tr[k], val);
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
860 KB |
Output is correct |
2 |
Correct |
3 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
856 KB |
Output is correct |
2 |
Correct |
2 ms |
856 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
5128 KB |
Output is correct |
2 |
Correct |
16 ms |
4052 KB |
Output is correct |
3 |
Correct |
29 ms |
6388 KB |
Output is correct |
4 |
Correct |
30 ms |
6140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
6180 KB |
Output is correct |
2 |
Correct |
20 ms |
4868 KB |
Output is correct |
3 |
Correct |
22 ms |
5436 KB |
Output is correct |
4 |
Correct |
30 ms |
6216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
6148 KB |
Output is correct |
2 |
Correct |
22 ms |
5496 KB |
Output is correct |
3 |
Correct |
22 ms |
5252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
141 ms |
29748 KB |
Output is correct |
2 |
Correct |
321 ms |
57568 KB |
Output is correct |
3 |
Correct |
75 ms |
18536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
137 ms |
31564 KB |
Output is correct |
2 |
Correct |
85 ms |
19064 KB |
Output is correct |
3 |
Correct |
270 ms |
52892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
97 ms |
23752 KB |
Output is correct |
2 |
Correct |
137 ms |
29740 KB |
Output is correct |
3 |
Correct |
101 ms |
23752 KB |
Output is correct |
4 |
Correct |
242 ms |
54608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
118 ms |
26268 KB |
Output is correct |
2 |
Correct |
102 ms |
24236 KB |
Output is correct |
3 |
Correct |
58 ms |
13444 KB |
Output is correct |
4 |
Correct |
266 ms |
53028 KB |
Output is correct |