이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi first
#define se second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
/** END OF TEMPLATE **/
const int mxN = 1e6 + 7;
struct DSU {
vector<int> e, p;
DSU(int t) : e(t+1, -1) {
p.resize(t+1);
FOR(i, 0, t) p[i] = i;
}
int rep(int u) { return e[u] < 0 ? u : e[u] = rep(e[u]); }
int get(int u) { return p[rep(u)]; }
void unite(int u, int v, bool st) {
u = rep(u); v = rep(v);
if(u == v) return;
if(e[u] > e[v]) swap(u, v);
e[u] += e[v]; e[v] = u;
if(st) p[u] = max(p[u], p[v]);
else p[u] = min(p[u], p[v]);
}
};
int l[mxN], r[mxN], pos[mxN];
int n, m;
int a[mxN], b[mxN], pi[mxN];
bool check(int st, int i, int j) {
if(!st) {
//cerr << i << ' ' << j << ' ' << a[i] << ' ' << a[i-r[j]] << '\n';
if(l[j] && i > l[j] && a[i - l[j]] > a[i]) return false;
if(r[j] && i > r[j] && a[i - r[j]] < a[i]) return false;
//cerr << '*';
return true;
} else {
if(j == n+1) return false;
if(l[j] && i > l[j] && b[i - l[j]] > b[i]) return false;
if(r[j] && i > r[j] && b[i - r[j]] < b[i]) return false;
return true;
}
}
void calc() {
DSU L(n+2), R(n+2);
pos[0] = 0, pos[n+1] = n+1;
FORD(i, n, 1) {
int u = a[i];
int t1 = pos[L.get(u-1)], t2 = pos[R.get(u+1)];
if(t1) l[i] = i - t1;
if(t2 < n+1) r[i] = i - t2;
L.unite(u, u-1, 0);
R.unite(u, u+1, 1);
}
// cerr << "\nL: ";
// FOR(i, 1, n) cout << l[i] << ' ';
// cerr << "\nR: ";
// FOR(i, 1, n) cout << r[i] << ' ';
// cerr << '\n';
}
int main()
{
FastIO;
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
cin >> n >> m;
FOR(i, 1, n) {
cin >> pos[i];
a[pos[i]] = i;
}
vector<int> t;
FOR(i, 1, m) cin >> b[i], t.PB(b[i]);
sort(ALL(t));
FOR(i, 1, m)
b[i] = lower_bound(ALL(t), b[i]) - t.begin() + 1;
calc();
FOR(i, 2, n) {
int j = pi[i-1];
while(j > 0 && !check(0, i, j+1))
j = pi[j];
if(check(0, i, j+1)) j++;
pi[i] = j;
}
int j = 0;
vector<int> res;
FOR(i, 1, m) {
while(j > 0 && !check(1, i, j+1))
j = pi[j];
if(check(1, i, j+1)) j++;
if(j == n) res.PB(i - n + 1);
}
cout << res.size() << '\n';
for(auto &x : res) cout << x << ' ';
return 0;
}
/*
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |