record

尝试将 #9 1.04s -> 1.00s

有没有什么方法吗？

Code:

#include <bits/stdc++.h>
using namespace std;

int a[1000005];

int max_ans[1000005], min_ans[1000005];
map<int, int> data;

int main() {
	ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int right = k+1;
	for (int i = 1; i <= k; i++) {
		if (data.find(a[i]) != data.end()) {
			data[a[i]]++;
		} else {
			data[a[i]] = 1;
		}
	}
	min_ans[1] = data.begin()  -> first;
	max_ans[1] = data.rbegin() -> first;

	while (right <= n){
		map<int, int>::iterator last_iter = data.find(a[right-k]), 
								this_iter = data.find(a[right]);
		(last_iter -> second)--;
		if ((last_iter -> second) == 0) {
			data.erase(last_iter);
		}
		if (this_iter == data.end()) {
			data[a[right]] = 1;
		} else {
			(this_iter -> second)++;
		}
		min_ans[right-k+1] = data.begin()  -> first;
		max_ans[right-k+1] = data.rbegin() -> first;
		right++;
	}
	for (int i = 1; i <= n-k+1; i++) {
		cout << min_ans[i] << ' ';
	}
	cout << endl;
	for (int i = 1; i <= n-k+1; i++) {
		cout << max_ans[i] << ' ';
	}
	return 0;
}