求卡常

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;
}