Editorial for Bedao Mini Contest 09 - CNTDIFF


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Sử dụng một map để duy trì số lượng số trong một đoạn gồm ~k~ bông hoa. Với mỗi ~i~ ~(i \ge k + 1)~ ta sẽ thực hiện hai thao tác trừ đi số ở vị trí ~i - k~ và cộng map lên số ở vị trí ~i~. Với mỗi thao tác update, xét nếu số đó xuất hiện đúng ~1~ lần thì số lượng số khác nhau nhiều nhất tăng lên ~1~, hoặc ngược lại nếu số đó không còn tồn tại trong map.

Độ phức tạp: ~O(NlogN)~

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

const int N = 3e5 + 5;
int n, k, a[N];
set<int> se;
map<int, int> mp;

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> k;
    for1(i,1,n) cin >> a[i];

    for1(i,1,k) {
        se.insert(a[i]);
        mp[a[i]]++;
    }

    int res = sz(se);
    for1(i,k + 1,n) {
        mp[a[i - k]]--;
        if (!mp[a[i - k]]) se.erase(a[i - k]);
        if (!mp[a[i]]) se.insert(a[i]);
        mp[a[i]]++;
        res = max(res, sz(se));
    }
    cout << res;

}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.