이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
int const MOD = 1e9 + 7;
ll const baza = 997;
ll potf(ll n, int k) {
ll ret = 1;
while (k) {
if (k % 2) {
ret *= n;
ret %= MOD;
}
n *= n;
n %= MOD;
k /= 2;
}
return ret;
}
template<class T>
struct BIT{
vector<T> bit;
explicit BIT(int N) : bit(N, 0) {}
void add(int pos, T val) {
for (; pos < (int) bit.size(); pos += pos & -pos) {
bit[pos] += val;
bit[pos] %= MOD;
}
}
T sum(int r) {
T res{};
for (; r > 0; r -= r & -r) {
res += bit[r];
res %= MOD;
}
return res;
}
T sum(int l, int r) {
T ret = sum(r) - sum(l - 1);
ret %= MOD;
if (ret < 0) ret += MOD;
return ret;
}
};
ll divmod(ll a, ll b) {
return (a * potf(b, MOD - 2)) % MOD;
}
vector<int> v;
vector<ll> potinv, potreg, nxt, prv;
vector<int> ans, ord, ordb;
oset<int> s;
BIT<ll> bit(1);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
potinv.resize(m + 10);
potreg.resize(m + 10);
potreg[0] = 1;
for (int i = 1; i < m + 10; ++i) {
potreg[i] = (potreg[i - 1] * baza) % MOD;
}
potinv[0] = 1;
ll divtmp = divmod(1, baza);
for (int i = 1; i < m + 10; ++i) {
potinv[i] = (potinv[i - 1] * divtmp) % MOD;
}
ll fh = 0;
{
vector<int> p(n);
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
--a;
p[a] = i + 1;
}
fh = 0;
for (auto a : p) {
fh *= baza;
fh += a;
fh %= MOD;
}
}
v.resize(m);
for (auto &a : v) cin >> a;
vector<int> tmp = v;
sort(begin(tmp), end(tmp));
tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));
for (auto &a : v) {
a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
}
bit.bit.resize(m + 10, 0);
ll pot = 1;
for (int i = m - 1; i > m - n; --i) {
bit.add(v[i], pot);
pot *= baza;
pot %= MOD;
}
nxt.resize(m + 10), prv.resize(m + 10);
int divi = 0;
for (int i = m - n; i >= 0; --i) {
nxt[i] = (bit.sum(v[i] + 1, m + 9) * potinv[divi]) % MOD;
bit.add(v[i + n - 1], -potreg[divi]);
bit.add(v[i], pot);
pot *= baza;
pot %= MOD;
divi++;
prv[i + n - 1] = (bit.sum(v[i + n - 1] + 1, m + 9) * potinv[divi]) % MOD;
}
ll h = 0;
{
vector<int> fix(n);
for (int i = 0; i < n; ++i) {
fix[i] = v[i];
}
tmp = fix;
sort(begin(tmp), end(tmp));
tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));
for (auto &a : fix) {
a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
}
for (int i = 0; i < n; ++i) {
h *= baza;
h += fix[i];
h %= MOD;
}
}
tmp.clear();
ord.resize(m), ordb.resize(m);
for (int i = m - 1; i > m - n; --i) {
s.insert(v[i]);
}
for (int i = m - n; i >= 0; --i) {
ord[i] = s.order_of_key(v[i]) + 1;
s.insert(v[i]);
s.erase(v[i + n - 1]);
}
s.clear();
for (int i = 0; i < n - 1; ++i) {
s.insert(v[i]);
}
for (int i = n - 1; i < m; ++i) {
ordb[i] = s.order_of_key(v[i]) + 1;
s.insert(v[i]);
s.erase(v[i - n + 1]);
}
v.clear();
s.clear();
ans.reserve(n / 2);
if (fh == h) ans.push_back(0);
ll rem = potreg[n - 1];
for (int i = n; i < m; ++i) {
h -= rem * ord[i - n];
h %= MOD;
h -= nxt[i - n];
h %= MOD;
h += prv[i];
h %= MOD;
if (h < 0) h += MOD;
h *= baza;
h += ordb[i];
h %= MOD;
if (h < 0) h += MOD;
if (fh == h) {
ans.push_back(i - n + 1);
}
}
cout << ans.size() << '\n';
for (auto a : ans) cout << a + 1 << ' ';
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... |