이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define lli long long
#define fi first
#define se second
#define maxi(a, b) a = max(a, b)
#define mize(a, b) a = min(a, b)
#define getbit(a, i) ((a) >> (i) & 1)
#define FOR(i, a, b) for(int i=a, _n=b; i<=_n; ++i)
#define FORD(i, a, b) for(int i=a, _n=b; i>=_n; --i)
#define REP(i, _n) for(int i=0; i<_n; ++i)
#define sz(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
#define ii pair<int, int>
using namespace std;
typedef long long hash_type;
const int N = 2e5+5;
const hash_type MOD = 1e9+7;
int n, q;
string s;
hash_type it1[N*4], it2[N*4], bs[N];
// it1 - left to right, left * base + right
// it2 - right to left, right * base + left
template <typename T, int SZ>
struct PST {
struct Node {
T val;
int c[2];
Node() {
val = 0;
c[0] = c[1] = 0;
}
};
static const int LIM = 5e6;
Node d[LIM];
int nxt = 0;
int copy(int t) { d[nxt] = d[t]; return nxt++; }
T comb(const T& a, const T& b) { return a + b; }
void pull(int c) { d[c].val = comb(d[d[c].c[0]].val, d[d[c].c[1]].val); }
T query(int lo, int hi, int t, int l, int r) {
if (lo >= r || hi <= l) return 0;
if (lo <= l && r <= hi) return d[t].val;
int m = (l + r) / 2;
T lef = query(lo, hi, d[t].c[0], l, m);
T rig = query(lo, hi, d[t].c[1], m, r);
return comb(lef, rig);
}
int upd(int i, const T& v, int t, int l, int r) {
int x = copy(t);
if (r - l == 1) {
d[x].val = v;
return x;
}
int m = (l + r) / 2;
if (i < m) {
d[x].c[0] = upd(i, v, d[x].c[0], l, m);
}else{
d[x].c[1] = upd(i, v, d[x].c[1], m, r);
}
pull(x);
return x;
}
int build(const vector<T>& a, int l, int r) {
int c = nxt++;
if (r - l == 1) {
if (l < (int)a.size()) d[c].val = a[l];
return c;
}
int m = (l + r) / 2;
d[c].c[0] = build(a, l, m);
d[c].c[1] = build(a, m, r);
pull(c);
return c;
}
vector<int> rts;
void update_time(int i, const T& v) {
rts.pb(upd(i, v, rts.back(), 0, SZ));
}
void build(const vector<T>& a) {
rts.pb(build(a, 0, SZ));
}
T query_time(int ti, int lo, int hi) {
return query(lo, hi, rts[ti], 0, SZ);
}
int order_of(int t1, int t2, int x, int l, int r) {
//gets count <=
if (r - l == 1) {
if (l > x) return 0;
return d[t1].val - d[t2].val;
}
int m = (l + r) / 2;
if (x < m) {
return order_of(d[t1].c[0], d[t2].c[0], x, l, m);
}
int on_left = d[d[t1].c[0]].val - d[d[t2].c[0]].val;
return on_left + order_of(d[t1].c[1], d[t2].c[1], x, m, r);
}
int order_of(int t1, int t2, int x) {
int ret = order_of(rts[t1], rts[t2], x, 0, SZ);
return ret;
}
};
PST<int, 1 << 20> pst;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (auto& u : a) {
cin >> u;
u--;
}
vector<int> c = a;
for (int i = 0; i < n; i++) {
c[a[i]] = i;
}
a = c;
for (auto& u : a) u++;
for (auto& u : b)
cin >> u;
c = b;
sort(all(c));
c.erase(unique(all(c)), c.end());
for (auto& u : b) {
u = lower_bound(all(c), u) - c.begin();
}
c.clear();
vector<int> fen(n + 1);
auto prefix = [&](int g) -> int {
int ret = 0;
for (; g > 0; g -= g & -g)
ret += fen[g];
return ret;
};
auto up_fen = [&](int g) -> void {
for (; g <= n; g += g&-g)
fen[g] += 1;
};
vector<int> order_stat(n);
for (int i = 0; i < n; i++) {
order_stat[i] = prefix(a[i]);
up_fen(a[i]);
}
#ifdef LOCAL
cout << "A:\n";
for (auto u : a)
cout << u << " ";
cout << "\n";
cout << "Order stat:\n";
for (auto u : order_stat)
cout << u << " ";
cout << "\n";
cout << "\n";
#endif
pst.build(vector<int>(n + 1, 0));
int original_root = (int)pst.rts.size() - 1;
vector<int> root_times(n);
auto order_of = [&](int l, int r, int x) -> int {
int ret = pst.order_of(root_times[r], (l ? root_times[l - 1] : original_root), x);
return ret;
};
vector<int> kmp(n);
for (int i = 1; i < n; i++) {
int j = kmp[i - 1];
while (j >= 0) {
//check j + 1
if (j == 0 or order_of(i - j, i - 1, a[i]) == order_stat[j]) {
kmp[i] = j + 1;
break;
}
j = kmp[j - 1];
}
pst.update_time(a[i], 1);
root_times[i] = (int)pst.rts.size() - 1;
}
#ifdef LOCAL
cout << "A KMP: ";
for (auto u : kmp) cout << u << " ";
cout << '\n';
#endif
pst.rts.clear();
pst.nxt = 0;
pst.build(vector<int>(m + 1, 0));
original_root = (int)pst.rts.size() - 1;
root_times = vector<int>(m, 0);
vector<int> kmp_b(m);
vector<int> ans;
int prev_kmp = 0;
for (int i = 0; i < m; i++) {
int j = prev_kmp;
while (j >= 0) {
if (j != n and (j == 0 or order_of(i - j, i - 1, b[i]) == order_stat[j])) {
kmp_b[i] = j + 1;
break;
}
j = kmp[j - 1];
}
pst.update_time(b[i], 1);
root_times[i] = (int)pst.rts.size() - 1;
prev_kmp = kmp_b[i];
if (kmp_b[i] == n) {
ans.pb(i);
}
}
#ifdef LOCAL
cout << "B KMP: ";
for (auto u : kmp_b)
cout << u << " ";
cout << "\n";
#endif
cout << ans.size() << "\n";
for (auto u : ans)
cout << u + 1 - n + 1 << " ";
cout << '\n';
};
//Jelly1010
# | 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... |