| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 553431 | AugustinasJucas | Matching (CEOI11_mat) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2")
using namespace std;
int n, m;
vector<int> a, b;
const int mod = 1e9 + 7;
const long long maxN = 1000000 ;
const int dydis = 1e6 + 10;
vector<long long> pw;
struct treap {
int dbInd = 0;
vector<int> l, r, w;
vector<int> val, myInd, sz;
vector<int> subHash;
int rt = -1;
treap() {
pw.resize(dydis);
l.resize(dydis);
r.resize(dydis);
w.resize(dydis);
val.resize(dydis);
myInd.resize(dydis);
subHash.resize(dydis);
sz.resize(dydis);
pw[0] = 1;
for(int i = 1; i < dydis; i++) {
pw[i] = 1ll * pw[i-1] * maxN % mod;
}
}
int newN(int Val, int Ind){
l[dbInd] = r[dbInd] = -1;
w[dbInd] = rand();
val[dbInd] = Val;
myInd[dbInd] = Ind;
subHash[dbInd] = Ind;
sz[dbInd] = 1;
return dbInd++;
}
int hMerge(int h1, int h2, int sz2){
int ret = h1;
ret = 1ll * ret * pw[sz2] % mod;
ret = (ret + h2) % mod;
return ret;
}
void upd(int v){
int hashL = 0, hashR = 0, hashMid;
int lsz = 0; int rsz = 0;
if(l[v] != -1) {
hashL = subHash[l[v]];
lsz = sz[l[v]];
}
if(r[v] != -1) {
hashR = subHash[r[v]];
rsz = sz[r[v]];
}
hashMid = myInd[v];
sz[v] = lsz + 1 + rsz;
subHash[v] = (1ll*hashL * maxN%mod + hashMid)%mod;
subHash[v] = hMerge(subHash[v], hashR, rsz);
}
pair<int, int> split(int v, int vl) {
if(v == -1) return {-1, -1};
if(val[v] < vl) { // as kaireje puseje
auto ds = split(r[v], vl);
r[v] = ds.first;
upd(v);
return {v, ds.second};
}else { // as desineje puseje
auto kr = split(l[v], vl);
l[v] = kr.second;
upd(v);
return {kr.first, v};
}
}
int merge(int L, int R) {
if(R == -1) return L;
if(L == -1) return R;
if(w[L] > w[R]) {
int mr = merge(r[L], R);
r[L] = mr;
upd(L);
return L;
}else {
int mr = merge(L, l[R]);
l[R] = mr;
upd(R);
return R;
}
}
void print(int v = -2){
if(v == -2) v = rt;
if(v == -1) return ;
print(l[v]);
cout << "(val=" << val[v] << ", ind=" << myInd[v] << ") ";
print(r[v]);
}
void insert(int val, int ind) {
int nd = newN(val, ind);
auto prm = split(rt, val);
prm.first = merge(prm.first, nd);
rt = merge(prm.first, prm.second);
// cout << "rt tampa " << rt << endl;
}
void erase(int val) {
auto prm = split(rt, val+1);
auto ant = split(prm.first, val);
rt = merge(ant.first, prm.second);
}
int getHash() {
return subHash[rt];
}
};
treap medis;
int main ()
srand(time(0));
cin.tie(NULL);
ios_base::sync_with_stdio(false);
/*int sk = 5;
int indd = 0;
while(sk--) {
int val, ind;
cin >> val ;
medis.insert(val, indd++);
medis.print();
cout << ", bendras hashas = " << medis.getHash();
cout << endl;
}
sk = 5;
while(sk--) {
int val, ind;
cin >> val;
medis.erase(val, 0);
medis.print();
//cout << ", bendras hashas = " << medis.getHash();
//cout << endl;
}*/
cin >> n >> m;
a.resize(n);
b.resize(m);
for(int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
for(auto &x : b) {
cin >> x;
}
long long reikia = 0;
for(auto x : a) {
reikia = (1ll * reikia * maxN % mod + x) % mod;
}
//cout << "reikia = " << reikia << endl;
for(int i = 0; i < n; i++) {
medis.insert(b[i], i);
}
long long turi = 0;
for(int i = 0; i < n; i++) {
turi = (turi + pw[i]) % mod;
}
vector<int> ans;
if(medis.getHash() == reikia) {
ans.push_back(0);
}
for(int i = n; i < m; i++) {
medis.erase(b[i-n]);
medis.insert(b[i], i);
int hsh = ((medis.getHash() - 1ll * (i-n+1) * turi % mod) % mod + mod) % mod;
if(reikia == hsh) {
ans.push_back(i-n+1);
}
// cout << "nuo " << i << ", hsh = " << hsh << endl;
}
cout << ans.size() << "\n";
for(auto &x : ans) {
cout << x+1 << " ";
}
return 0;
}
/*
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
2 5
1 2
1 2 3 4 5
*/