Submission #836718

#	Time	Username	Problem	Language	Result	Execution time	Memory
836718		ToniB	Matching (CEOI11_mat)	C++17	0 / 100	2079 ms	65536 KiB

mat

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 2;
const int OFF = 1 << 21;

int n, m, tour[OFF];
int st[OFF][2];
vector<int> a, b, L, R, L_cur, R_cur, ans;

void con(int x, int l, int r, vector<int>& vals){
	if(l == r){
		tour[x] = l; return ;
	}
	int mid = (l + r) >> 1;
	con(x * 2 + 1, l, mid, vals); con(x * 2 + 2, mid + 1, r, vals);
	if(vals[tour[x * 2 + 1]] > vals[tour[x * 2 + 2]]) tour[x] = tour[x * 2 + 1];
	else tour[x] = tour[x * 2 + 2];
}
int f(int x, int l, int r, int ql, int qr, vector<int>& vals){
	if(ql > r || l > qr) return -1;
	if(ql <= l && r <= qr) return tour[x];
	int mid = (l + r) >> 1;
	int lval = f(x * 2 + 1, l, mid, ql, qr, vals), rval = f(x * 2 + 2, mid + 1, r, ql, qr, vals);
	if(lval == -1) return rval;
	if(rval == -1) return lval;
	if(vals[lval] > vals[rval]) return lval;
	return rval;
}
void make_tree(int l, int r, int node, vector<int>& a, vector<int>& L, vector<int>& R){
	if(l != node){
		L[node] = f(0, 0, (int)a.size() - 1, l, node - 1, a);
		make_tree(l, node - 1, L[node], a, L, R);
		L[node] = node - L[node];
	}
	if(r != node){
		R[node] = f(0, 0, (int)a.size() - 1, node + 1, r, a);
		make_tree(node + 1, r, R[node], a, L, R);
		R[node] = R[node] - node;
	}
}

void prepare(vector<int>& a, vector<int>& L, vector<int>& R){
	con(0, 0, (int)a.size() - 1, a);
	make_tree(0, (int)a.size() - 1, tour[0], a, L, R);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	a.resize(n); b.resize(m);
	vector<int> inv (n);
	for(int i = 0; i < n; ++i){
		cin >> a[i], --a[i];
		inv[a[i]] = i;
	}
	swap(a, inv);
	vector<int> cmp;
	unordered_map<int, int> um;
	for(int i = 0; i < m; ++i){
		cin >> b[i];
		cmp.push_back(b[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	
	for(int i = 0; i < (int)cmp.size(); ++i) um[cmp[i]] = i;

	for(int i = 0; i < m; ++i) b[i] = um[b[i]];
	
	L.resize(n); R.resize(n);
	L_cur.resize(m); R_cur.resize(m);

	prepare(a, L, R);
	vector<int> pre (n);
	for(int i = 0; i < n; ++i) pre[i] = b[i];

	prepare(pre, L_cur, R_cur);
	
	con(0, 0, m - 1, b);
	
	bool ok = 1;
	for(int i = 0; i < n; ++i){
		ok &= L[i] == L_cur[i];
		ok &= R[i] == R_cur[i];
	}
	if(ok) ans.push_back(0);
	
	for(int i = n; i < m; ++i){
//		int idx_R = f_st(0, 0, m - 1, b[i], m - 1, 1), idx_L = f_st(0, 0, m - 1, b[i - n], m - 1, 0);
		int idx_L = m + 1, idx_R = -1;
		for(int k = i - n + 1; k <= i; ++k){
			if(b[k] > b[i - n]){
				idx_L = k; break;
			}
		}
		for(int k = i; k >= i - n + 1; --k){
			if(b[k] > b[i]){
				idx_R = k; break;
			}
		}
		// idx_R = rightmost bigger than b[i], idx_L = leftmost bigger than b[i - n]
		if(idx_L != m + 1){
			assert(L_cur[idx_L] == idx_L - i + n);
			if(R_cur[i - n] == 0){
				L_cur[idx_L] = 0;
			} else L_cur[idx_L] -= R_cur[i - n];
		}
		if(idx_R == -1){
			// b[i] is new maximum
			int x = f(0, 0, m - 1, i - n + 1, i - 1, b);
			assert(b[i] > b[x]);
			L_cur[i] = i - x;
		} else {
			if(R_cur[idx_R] == 0) L_cur[i] = 0;
			else L_cur[i] = i - idx_R - R_cur[idx_R];
			R_cur[idx_R] = i - idx_R;
		}
		
		bool ok = 1;
		int p = 0;
		for(int j = i - n + 1; j <= i; ++j){
			ok &= L_cur[j] == L[p];
			ok &= R_cur[j] == R[p++];
		}
		if(ok) ans.push_back(i - n + 1);
	}
	cout << ans.size() << "\n";
	for(int x : ans) cout << x + 1 << " ";
	cout << "\n";
	return 0;
}

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