#include <bits/stdc++.h>
using namespace std;
#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, p[mxn], 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() {
sort(id, id + m + 1, [&] (int i, int j) {
return a[i] < a[j];
});
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 tl, tr;
int lazy, suma;
ll valo;
int power; // debug
tree *lc, *rc;
tree() {
power = 0;
tl = tr = 0;
lazy = valo = suma = 0;
lc = rc = NULL;
}
tree(int l, int r) {
power = 0;
tl = l, tr = r;
lazy = suma = valo = 0;
lc = rc = NULL;
}
void birth() {
if(tl == tr) return;
if(lc == NULL) lc = new tree(tl, (tl + tr) / 2);
if(rc == NULL) rc = new tree((tl + tr) / 2 + 1, tr);
}
int find_sum(int l, int r) {
int tm = (tl + tr) / 2;
if(tl == l && r == tr) return suma;
birth();
if(r <= tm) return lc-> find_sum(l, r);
if(tm < l) return rc-> find_sum(l, r);
int L = lc-> find_sum(l, tm);
int R = rc-> find_sum(tm + 1, r);
return L + R;
}
void pro() {
birth();
if(lazy == 0) return;
int d = abs(lazy);
if(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-> power += lazy;
rc-> power += lazy;
lc-> lazy += lazy;
rc-> lazy += lazy;
lazy = 0;
}
void merge() {
suma = lc-> suma + rc-> suma;
valo = (lc-> valo + rc-> valo) % mod;
}
void upt_add(int i, int x, int d) {
// birth();
if(tl == tr) {
power = d;
valo = x;
suma = 1;
return;
}
pro();
int tm = (tl + tr) / 2;
if(i <= tm) {
lc-> upt_add(i, x, d);
rc-> lazy++;
rc-> power++;
rc-> valo = rc-> valo * pw[1] % mod;
}
else rc-> upt_add(i, x, d);
merge();
}
void upt_rem(int i) {
// birth();
if(tl == tr) {
valo = 0;
suma = 0;
return;
}
pro();
int tm = (tl + tr) / 2;
if(i <= tm) {
lc-> upt_rem(i);
rc-> lazy--;
rc-> power--;
rc-> valo = rc-> valo * in[1] % mod;
}
else rc-> upt_rem(i);
merge();
}
int query(int l, int r) {
if(tl == l && r == tr) return valo;
int tm = (tl + tr) / 2; pro();
if(r <= tm) return lc-> query(l, r);
if(tm < l) return rc-> query(l, r);
int L = lc-> query(l, tm);
int R = rc-> query(tm + 1, r);
return (L + R) % mod;
}
} *root;
void add(int id, int a) {
int d = root-> find_sum(0, id);
root-> upt_add(id, a * pw[d + 1] % mod, d + 1);
}
signed main() {
cin.tie(0)-> sync_with_stdio(0);
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> p[i];
// p[i]--;
}
for(int i = 1; i <= m; i++) {
cin >> a[i];
id[i] = i;
}
if(n > 2e5) return 1;
init();
root = new tree(0, m);
// root-> build();
for(int i = 0; i <= m; i++)
pl[id[i]] = i;
for(int i = 0; i < n && i <= m; i++)
add(pl[i], i);
ll K = 0;
for(int i = 0; i < n; i++) {
ll t = p[i] * pw[i] % mod;
K = (K + t) % mod;
}
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]);
add(pl[r], r);
ll Q = root-> query(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);
// free(&t);
// free(&Q);
}
cout << ans.size() << endl;
for(int i : ans) cout << i << ' ';
cout << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
23128 KB |
Output is correct |
2 |
Correct |
7 ms |
23132 KB |
Output is correct |
3 |
Correct |
8 ms |
23132 KB |
Output is correct |
4 |
Correct |
7 ms |
23128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
25436 KB |
Output is correct |
2 |
Correct |
8 ms |
23132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
28248 KB |
Output is correct |
2 |
Correct |
20 ms |
27736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
28252 KB |
Output is correct |
2 |
Correct |
20 ms |
28252 KB |
Output is correct |
3 |
Correct |
10 ms |
25692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
151 ms |
55428 KB |
Output is correct |
2 |
Correct |
150 ms |
57172 KB |
Output is correct |
3 |
Correct |
296 ms |
58560 KB |
Output is correct |
4 |
Correct |
324 ms |
58408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
183 ms |
58716 KB |
Output is correct |
2 |
Correct |
314 ms |
58732 KB |
Output is correct |
3 |
Correct |
160 ms |
57808 KB |
Output is correct |
4 |
Correct |
144 ms |
61376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
158 ms |
58316 KB |
Output is correct |
2 |
Correct |
155 ms |
57984 KB |
Output is correct |
3 |
Correct |
178 ms |
57932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
92 ms |
27464 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
87 ms |
27212 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
229 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
183 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |