제출 #1202460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202460		SSKMF	Matching (CEOI11_mat)	C++20	100 / 100	569 ms	42432 KiB

mat

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

const int mod(998244353);
const int baza(13);

pair <int , int> arbore[2000000] , copie[1000001];
int putere[1000001] , sir[1000001] , luat[1000001];

inline void Update (const int nod , const int stanga , const int dreapta , const int valoare , const int tip)
{
    if (stanga == dreapta)
    {
        if (tip == -1) { arbore[nod] = { }; }
        else { arbore[nod] = {1 , tip}; }
        return;
    }

    const int mijloc = (stanga + dreapta) >> 1;
    if (valoare <= mijloc) { Update(nod + 1 , stanga , mijloc , valoare , tip); }
    else { Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , valoare , tip); }

    arbore[nod].first = arbore[nod + 1].first + arbore[nod + ((mijloc - stanga + 1) << 1)].first;
    arbore[nod].second = (1LL * arbore[nod + 1].second * putere[arbore[nod + ((mijloc - stanga + 1) << 1)].first] + arbore[nod + ((mijloc - stanga + 1) << 1)].second) % mod;
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    putere[0] = 1;
    for (int indice = 1 ; indice <= 1000000 ; indice++)
        { putere[indice] = 1LL * putere[indice - 1] * baza % mod; }

    int lungime_secventa , lungime;
    cin >> lungime_secventa >> lungime;

    int dorit = 0 , termen = 0;
    for (int indice = 1 ; indice <= lungime_secventa ; indice++)
    {
        int valoare;
        cin >> valoare;

        dorit = (1LL * dorit * baza + valoare) % mod;
        termen = (1LL * termen * baza + 1) % mod;
    }

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> sir[indice]; copie[indice] = {sir[indice] , indice}; }

    sort(copie + 1 , copie + lungime + 1);

    for (int indice = 1 ; indice <= lungime ; indice++)
        { sir[copie[indice].second] = indice; }

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        if (lungime_secventa < indice)
        { 
            Update(1 , 1 , lungime , sir[indice - lungime_secventa] , -1);
            (dorit += termen) %= mod;
        }

        Update(1 , 1 , lungime , sir[indice] , indice);

        if (arbore[1].second == dorit)
            { luat[++luat[0]] = indice - lungime_secventa + 1; }
    }

    cout << luat[0] << '\n';

    for (int indice = 1 ; indice <= luat[0] ; indice++)
        { cout << luat[indice] << ' '; }

    return 0;
}

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