이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define tm (tl + tr) / 2
#define int long long
using ll = long long;
const int base = 137;
const int mxn = 1e6 + 7;
const ll mod = 1e9 + 7;
int m, a[mxn], id[mxn];
int n, pl[mxn];
long long in[mxn], pw[mxn];
ll fpow(ll a, int n) {
if(n == 0) return 1;
if(n == 1) return a;
int t = fpow(a * a % mod, n / 2);
if(n % 2 == 0) return t;
return t * a % mod;
}
ll inverse(ll a) {
return fpow(a, mod - 2);
}
void init() {
pw[0] = in[0] = 1;
pw[1] = base;
in[1] = inverse(base);
for(int i = 1; i < mxn; i++) {
pw[i] = pw[i - 1] * pw[1] % mod;
in[i] = in[i - 1] * in[1] % mod;
}
}
struct tree {
int lazy, suma;
ll valo;
int power; // debug
tree() {
power = 0;
// tl = tr = 0;
lazy = valo = suma = 0;
}
};
tree st[mxn * 4];
int find_sum(int id, int tl, int tr, int l, int r) {
if(tl == l && r == tr) return st[id].suma;
if(r <= tm) return find_sum(id * 2 + 1, tl, tm, l, r);
if(tm < l) return find_sum(id * 2 + 2, tm + 1, tr, l, r);
int L = find_sum(id * 2 + 1, tl, tm, l, tm);
int R = find_sum(id * 2 + 2, tm + 1, tr, tm + 1, r);
return L + R;
}
void pro(int id) {
tree &self = st[id];
tree &lc = st[id * 2 + 1];
tree &rc = st[id * 2 + 2];
if(self.lazy == 0) return;
int d = abs(self.lazy);
if(self.lazy < 0) {
lc.valo = lc.valo * in[d] % mod;
rc.valo = rc.valo * in[d] % mod;
}
else {
lc.valo = lc.valo * pw[d] % mod;
rc.valo = rc.valo * pw[d] % mod;
}
lc.lazy += self.lazy;
rc.lazy += self.lazy;
self.lazy = 0;
}
void merge(int id) {
tree &self = st[id];
tree &lc = st[id * 2 + 1];
tree &rc = st[id * 2 + 2];
self.suma = lc.suma + rc.suma;
self.valo = (lc.valo + rc.valo) % mod;
}
void upt_add(int id, int tl, int tr, int i, int x, int d) {
tree &self = st[id];
tree &rc = st[id * 2 + 2];
if(tl == tr) {
self.valo = x;
self.suma = 1;
return;
}
pro(id);
if(i <= tm) {
upt_add(id * 2 + 1, tl, tm, i, x, d);
rc.lazy++;
rc.valo = rc.valo * pw[1] % mod;
}
else upt_add(id * 2 + 2, tm + 1, tr, i, x, d);
merge(id);
}
void upt_rem(int id, int tl, int tr, int i) {
tree &self = st[id];
tree &rc = st[id * 2 + 2];
if(tl == tr) {
self.valo = 0;
self.suma = 0;
return;
}
pro(id);
if(i <= tm) {
upt_rem(id * 2 + 1, tl, tm, i);
rc.lazy--;
rc.valo = rc.valo * in[1] % mod;
}
else upt_rem(id * 2 + 2, tm + 1, tr, i);
merge(id);
}
int query(int id, int tl, int tr, int l, int r) {
if(tl == l && r == tr) return st[id].valo;
pro(id);
if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);
int L = query(id * 2 + 1, tl, tm, l, tm);
int R = query(id * 2 + 2, tm + 1, tr, tm + 1, r);
return (L + R) % mod;
}
void add(int id, int a) {
// int d = root-> find_sum(0, id);
int d = find_sum(0, 0, m, 0, id);
// root-> upt_add(id, a * pw[d + 1] % mod, d + 1);
upt_add(0, 0, m, id, a * pw[d + 1] % mod, d + 1);
}
signed main() {
cin.tie(0)-> sync_with_stdio(0);
cin >> n >> m;
init();
ll K = 0;
int azaa;
for(int i = 0; i < n; i++) {
cin >> azaa;
ll t = azaa * pw[i] % mod;
K = (K + t) % mod;
}
for(int i = 1; i <= m; i++) {
cin >> a[i];
id[i] = i;
}
sort(id, id + m + 1, [&] (int i, int j) {
return a[i] < a[j];
});
for(int i = 0; i <= m; i++)
pl[id[i]] = i;
for(int i = 0; i < n && i <= m; i++)
add(pl[i], i);
const ll T = (pw[n] - 1) * inverse(base - 1) % mod;
vector<int> ans;
for(int l = 1; l <= m; l++) {
int r = l + n - 1;
if(r > m) break;
// root-> upt_rem(pl[l - 1]);
upt_rem(0, 0, m, pl[l - 1]);
add(pl[r], r);
// ll Q = root-> query(0, m);
ll Q = query(0, 0, m, 0, m);
ll t = l - 1;
t = t * T % mod;
t = (t + K) % mod;
t = t * base % mod;
if(t == Q) ans.push_back(l); }
cout << ans.size() << endl;
for(int i : ans) cout << i << ' ';
cout << endl;
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... |