Submission #1202460

#TimeUsernameProblemLanguageResultExecution timeMemory
1202460SSKMFMatching (CEOI11_mat)C++20
100 / 100
569 ms42432 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...