SCPC 2020 1차예선 4번 구현 소스 코드

풀이 설명은 https://paido.tistory.com/21을 참고해 주세요.

 

 

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <queue>
#include <math.h>
#include <memory.h>
 
 
int readInt();
long long readLong();
 
 
int N, K, M;
char S[50002];
 
 
void GatherInput() {
    N = readInt();
    K = readInt();
    M = readInt();
    scanf("%s", S + 1);
    for (int i = 1; i <= N; i++) S[i] -= '0';
}
 
 
struct SegTree {
    int Count;
    int Tree[1048577], Lazy[1048577];
 
    void Init(int Count) {
        this->Count = Count;
        memset(Tree, 0, sizeof(Tree));
        memset(Lazy, 0, sizeof(Lazy));
    }
    void Update(int Start, int End, int Delta) {
        UpdateInternal(Start, End, 1, 1, Count, Delta);
    }
    int Query() {
        return QueryInternal(1, Count, 1, 1, Count);
    }
 
private:
    void UpdateInternal(int Start, int End, int TPos, int TL, int TR, int Delta) {
        if (End < TL || TR < Start) return;
        if (Start <= TL && TR <= End) {
            /* Lazy update */
            Lazy[TPos] += Delta;
        }
        else {
            /* Propagate down the Lazy if it exists */
            Lazy[2 * TPos] += Lazy[TPos];
            Lazy[2 * TPos + 1] += Lazy[TPos];
            Lazy[TPos] = 0;
 
            /* Propagate */
            int TMid = (TL + TR) / 2;
            UpdateInternal(Start, End, 2 * TPos, TL, TMid, Delta);
            UpdateInternal(Start, End, 2 * TPos + 1, TMid + 1, TR, Delta);
 
            /* Update */
            Tree[TPos] = std::max(Tree[2 * TPos] + Lazy[2 * TPos],
                Tree[2 * TPos + 1] + Lazy[2 * TPos + 1]);
        }
    }
    int QueryInternal(int Start, int End, int TPos, int TL, int TR) {
        /* these two checks will automatically trap if TL == TR */
        if (End < TL || TR < Start) return std::numeric_limits<int>::min();
        if (Start <= TL && TR <= End) return Tree[TPos] + Lazy[TPos];
 
        /* Propagate down the Lazy if it exists */
        Lazy[2 * TPos] += Lazy[TPos];
        Lazy[2 * TPos + 1] += Lazy[TPos];
        Tree[TPos] += Lazy[TPos];
        Lazy[TPos] = 0;
 
        int TMid = (TL + TR) / 2;
        return std::max(QueryInternal(Start, End, TPos * 2, TL, TMid),
            QueryInternal(Start, End, TPos * 2 + 1, TMid + 1, TR));
    }
} ST;
 
int ToNum(char* F) {
    int num = 0;
    for (int i = 1; i <= K; i++) {
        num *= 10;
        num += F[i];
    }
    return num;
}
 
int P;
int A[500001], ACnt[500001];
int B[500001];
 
void Solve() {
    char c = 1;
 
    /* step 1 */
    std::vector<int> Nums, NumsAll;
 
    auto try_push = [&](char* F, std::vector<int>& Target) {
        int num = ToNum(F);
        Target.push_back(num);
    };
 
    for (int i = 1; i + K - 1 <= N; i++) {
        char* F = S + i - 1; // still 1-based
 
        /* normal case */
        try_push(F, Nums);
        try_push(F, NumsAll);
 
        /* changing to 1 case */
        for (int j = 1; j <= K; j++) {
            std::swap(c, F[j]);
            try_push(F, NumsAll);
            std::swap(c, F[j]);
        }
    }
 
    std::sort(NumsAll.begin(), NumsAll.end());
    int prev = A[0] = -1; // to mark nonexistence and make A[0] < A[1] for binary search
    P = 0;
    for (auto x : NumsAll) {
        if (x > prev) {
            P++;
            A[P] = x;
            ACnt[P] = 0;
            prev = x;
        }
    }
    std::sort(Nums.begin(), Nums.end());
    int q = 0;
    for (auto x : Nums) {
        while (A[q] != x) q++;
        ACnt[q]++;
    }
 
    /* step 2,3 */
    int left = 1;
    for (int i = 1; i <= P; i++) {
        while (left < i && (A[i] - A[left] > M)) left++;
        B[i] = left;
    }
 
    /* step 4,5 */
    ST.Init(P);
    for (int i = 1; i <= P; i++) {
        ST.Update(B[i], i, +ACnt[i]);
    }
 
    /* step 6 */
    int opt = ST.Query();
 
    /* step 7 */
    auto Num2Idx = [](int num) -> int {
        auto p = std::lower_bound(A, A + P, num);
        return (p - A);
    };
 
    std::vector<std::pair<int, int>> DeltaList;
    for (int i = 1; i <= N; i++) {
        for (int j = i - K + 1; j <= i; j++) {
            if (j >= 1 && j + K - 1 <= N) {
                char* F = S + j - 1;
                int num = ToNum(F);
                DeltaList.push_back(std::make_pair(Num2Idx(num), -1));
            }
        }
        std::swap(c, S[i]);
        for (int j = i - K + 1; j <= i; j++) {
            if (j >= 1 && j + K - 1 <= N) {
                char* F = S + j - 1;
                int num = ToNum(F);
                DeltaList.push_back(std::make_pair(Num2Idx(num), +1));
            }
        }
        std::swap(c, S[i]);
 
        /* apply */
        for (auto p : DeltaList) ST.Update(B[p.first], p.first, +p.second);
 
        /* query */
        opt = std::max(opt, ST.Query());
 
        /* undo */
        for (auto p : DeltaList) ST.Update(B[p.first], p.first, -p.second);
 
        /* clear */
        DeltaList.clear();
    }
 
    /* step 8 */
    printf("%d\n", opt);
}
 
 
 
int main() {
#ifdef BOJ
    int T = readInt();
#else
    int T = readInt();
    setbuf(stdout, NULL);
#endif
    for (int test_case = 1; test_case <= T; test_case++) {
        GatherInput();
#ifndef BOJ
        printf("Case #%d\n", test_case);
#endif
        Solve();
    }
    return 0;
}
 
int readInt() {
    int p;
    scanf("%d", &p);
    return p;
}
 
long long readLong() {
    long long p;
    scanf("%lld", &p);
    return p;
}