이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//In the name of God
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 4e6 + 10;
ll k, n, m;
ll P[MXN], plc[MXN], A[MXN];
ll Fen[MXN], lps[MXN], M[MXN];
vector<ll> Num;
inline int GetId(ll x){
return lower_bound(Num.begin(), Num.end(), x) - Num.begin() + 1;
}
void Upd(ll p, ll x){ p ++;
for(; p < MXN; p += p & -p) Fen[p] += x;
}
ll Get(ll p){ p ++;
ll r = 0;
for(; p; p -= p & -p) r += Fen[p];
return r;
}
void LPS(){
ll k = (lps[0] = lps[1] = 0);
for(int i = 2; i <= m; i ++){
if(M[i] == -1){
for(int j = i - k; j < i; j ++) Upd(M[j], -1);
lps[i] = k = 0;
continue;
}
while(k && plc[k + 1] != Get(M[i])){
for(int j = i - k; j < i - lps[k]; j ++) Upd(M[j], -1);
k = lps[k];
}
if(plc[k + 1] == Get(M[i])){
k ++, Upd(M[i], 1);
}
lps[i] = k;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> k >> n;
for(int i = 1, x; i <= k; i ++) cin >> x, P[x] = i;
for(int i = 1; i <= n; i ++) cin >> A[i], Num.push_back(A[i]);
//sort(Num.begin(), Num.end());
//for(int i = 1; i <= n; i ++) A[i] = GetId(A[i]);
for(int i = 1; i <= k; i ++){
plc[i] = Get(P[i]);
Upd(P[i], 1);
}
plc[k + 1] = -1;
for(int i = 1; i <= k; i ++) M[++ m] = P[i];
M[++ m] = -1;
for(int i = 1; i <= n; i ++) M[++ m] = A[i];
memset(Fen, 0, sizeof Fen);
LPS();
ll ans = 0; vector<ll> ANS;
for(int i = k + 2; i <= m; i ++){
ans += (lps[i] == k);
if(lps[i] == k) ANS.push_back(i - k - 1);
}
cout << ans << '\n';
for(auto X : ANS) cout << X - k + 1 << ' '; cout << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
mat.cpp: In function 'int main()':
mat.cpp:64:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
64 | for(auto X : ANS) cout << X - k + 1 << ' '; cout << '\n';
| ^~~
mat.cpp:64:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
64 | for(auto X : ANS) cout << X - k + 1 << ' '; cout << '\n';
| ^~~~
# | 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... |