// old code
#include <bits/stdc++.h>
using namespace std;
struct fwTree{
int node[1000005];
void clear(){
for(int i=1;i<=(int)1e6;i++)
node[i] = 0;
}
void upd(int pos,int val){
for(;pos<=(int)1e6;pos+=pos&-pos)
node[pos] += val;
}
int get(int pos){
int res = 0;
for(;pos;pos-=pos&-pos)
res += node[pos];
return res;
}
};
int getInt(){
char c;
int res = 0;
bool mark = 0;
while(c = getchar()){
if (c < '0' || '9' < c){
if (mark) break;
continue;
}
mark = 1;
res = res * 10 + (c - '0');
}
return res;
}
int n, m, a[2000005];
int val[1000005];
int prefixSuffix[2000005];
fwTree fw;
vector <int> nen;
int main(){
// input
n = getInt();
m = getInt();
for(int i=1;i<=n;i++)
a[getInt()] = i;
for(int i=1;i<=m;i++)
a[n+1+i] = getInt(),
nen.push_back(a[n+1+i]);
sort(nen.begin(), nen.end());
for(int i=1;i<=m;i++)
a[n+1+i] = lower_bound(nen.begin(), nen.end(), a[n+1+i]) + 1 - nen.begin();// cout << a[i+1+n] << ' '; cout << endl;
// val[i] = how many columns that are lower than column i when we consider only first i columns
for(int i=1;i<=n;i++){
val[i] = fw.get(a[i]);
fw.upd(a[i], 1);
}
// prefixSuffix[i] = longest suffix at i that equals to prefix
fw.clear();
int pivot = 2;
vector <int> res;
//cout << 0 << ' ';
for(int i=2;i<=n+m+1;i++){
if (i == n+1){
fw.clear();
prefixSuffix[i] = 0;
pivot = i+1;
//cout << 0 << ' ';
continue;
}
int tmp = prefixSuffix[i-1];
if (tmp == n){
while(pivot < i - prefixSuffix[tmp])
fw.upd(a[pivot], -1),
++ pivot;
tmp = prefixSuffix[tmp];
}
while(fw.get(a[i]) != val[tmp+1]){
while(pivot < i - prefixSuffix[tmp])
fw.upd(a[pivot], -1),
++ pivot;
tmp = prefixSuffix[tmp];
}
fw.upd(a[i], 1);
prefixSuffix[i] = tmp + 1;
//cout << prefixSuffix[i] << ' ';
if (i > n && prefixSuffix[i] == n)
res.push_back(i - n - 1 - n + 1);
}
//cout << endl;
printf("%d\n",res.size());
for(auto v: res) printf("%d ", v);
}
Compilation message
mat.cpp: In function 'int getInt()':
mat.cpp:27:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
while(c = getchar()){
~~^~~~~~~~~~~
mat.cpp: In function 'int main()':
mat.cpp:100:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n",res.size());
~~~~~~~~~~^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4216 KB |
Output is correct |
2 |
Correct |
6 ms |
4216 KB |
Output is correct |
3 |
Correct |
6 ms |
4216 KB |
Output is correct |
4 |
Correct |
6 ms |
4216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4216 KB |
Output is correct |
2 |
Correct |
6 ms |
4216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4856 KB |
Output is correct |
2 |
Correct |
14 ms |
4728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
4856 KB |
Output is correct |
2 |
Correct |
14 ms |
4728 KB |
Output is correct |
3 |
Correct |
7 ms |
4344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
8336 KB |
Output is correct |
2 |
Correct |
67 ms |
7764 KB |
Output is correct |
3 |
Correct |
127 ms |
9068 KB |
Output is correct |
4 |
Correct |
128 ms |
9704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
9036 KB |
Output is correct |
2 |
Correct |
114 ms |
7888 KB |
Output is correct |
3 |
Correct |
89 ms |
9056 KB |
Output is correct |
4 |
Correct |
79 ms |
10092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
9196 KB |
Output is correct |
2 |
Correct |
78 ms |
8812 KB |
Output is correct |
3 |
Correct |
101 ms |
8808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
540 ms |
23012 KB |
Output is correct |
2 |
Correct |
889 ms |
36672 KB |
Output is correct |
3 |
Correct |
388 ms |
18216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
515 ms |
22676 KB |
Output is correct |
2 |
Correct |
577 ms |
22884 KB |
Output is correct |
3 |
Correct |
873 ms |
31216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
464 ms |
23732 KB |
Output is correct |
2 |
Correct |
372 ms |
33708 KB |
Output is correct |
3 |
Correct |
545 ms |
20396 KB |
Output is correct |
4 |
Correct |
566 ms |
30940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
422 ms |
24248 KB |
Output is correct |
2 |
Correct |
542 ms |
20740 KB |
Output is correct |
3 |
Correct |
192 ms |
15588 KB |
Output is correct |
4 |
Correct |
681 ms |
32732 KB |
Output is correct |