Submission #446827

#	Time	Username	Problem	Language	Result	Execution time	Memory
446827		Nima_Naderi	Matching (CEOI11_mat)	C++14	100 / 100	850 ms	55788 KiB

mat

//In the name of God
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
 
typedef int ll;
const ll MXN = 2e6 + 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 kp = (lps[0] = lps[1] = 0);
	for(int i = 2; i <= m; i ++){
		if(M[i] == -1){
			for(int j = i - kp; j < i; j ++) Upd(M[j], -1);
			lps[i] = kp = 0;
			continue;
		}
		while(kp && plc[kp + 1] != Get(M[i])){
			for(int j = i - kp; j < i - lps[kp]; j ++) Upd(M[j], -1);
			kp = lps[kp];
		}
		if(plc[kp + 1] == Get(M[i])){
			kp ++, Upd(M[i], 1);
		}
		lps[i] = kp;
	}
}
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;
}

Compilation message (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';
      |                                              ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10