Submission #1202453

#TimeUsernameProblemLanguageResultExecution timeMemory
1202453SSKMFMatching (CEOI11_mat)C++20
100 / 100
711 ms54324 KiB
#include <bits/stdc++.h> using namespace std; mt19937_64 generator(439889232); const int mod_1(1000000007) , mod_2(998244353); const int baza_1(13) , baza_2(11); pair <int , int> putere[1000001]; pair < int , pair <int , int> > arbore[2000000]; pair <int , int> copie[1000001]; int 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 , 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.first = (1LL * arbore[nod + 1].second.first * putere[arbore[nod + ((mijloc - stanga + 1) << 1)].first].first + arbore[nod + ((mijloc - stanga + 1) << 1)].second.first) % mod_1; arbore[nod].second.second = (1LL * arbore[nod + 1].second.second * putere[arbore[nod + ((mijloc - stanga + 1) << 1)].first].second + arbore[nod + ((mijloc - stanga + 1) << 1)].second.second) % mod_2; } int main () { ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); putere[0] = {1 , 1}; for (int indice = 1 ; indice <= 1000000 ; indice++) { putere[indice].first = 1LL * putere[indice - 1].first * baza_1 % mod_1; putere[indice].second = 1LL * putere[indice - 1].second * baza_2 % mod_2; } int lungime_secventa , lungime; cin >> lungime_secventa >> lungime; pair <int , int> dorit = { } , termen = { }; for (int indice = 1 ; indice <= lungime_secventa ; indice++) { int valoare; cin >> valoare; dorit.first = (1LL * dorit.first * baza_1 + valoare) % mod_1; dorit.second = (1LL * dorit.second * baza_2 + valoare) % mod_2; termen.first = (1LL * termen.first * baza_1 + 1) % mod_1; termen.second = (1LL * termen.second * baza_2 + 1) % mod_2; } 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.first += termen.first) %= mod_1; (dorit.second += termen.second) %= mod_2; } 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...