Submission #347401

#	Time	Username	Problem	Language	Result	Execution time	Memory
347401		saral	Matching (CEOI11_mat)	C++14	0 / 100	920 ms	46560 KiB

mat

#include <bits/stdc++.h>

using namespace std;
#define lli long long int
const int N = 1000100;
const lli MOD=1e9+7;
int t, n, m, br=-1;
lli a[N], b[N], d;
vector<lli>v, poc, sol;
lli f[N], active[N];
lli B=1e6+3, hesh, sub;
lli pot[N], upd;

lli powmod (lli a, lli x) {
	lli rez=1;
	while (x) {
		if (x%2) {
			rez = ((rez%MOD)*(a%MOD))%MOD;
		}
		a = ((a%MOD)*(a%MOD))%MOD;
		x/=2;
	}
	return rez;
}

lli divide (lli a, lli b) {
	return a * powmod(b, MOD-2) % MOD;
}

lli sum (int x) {
    if (!x) return 0;
    lli zbr=0;
    for (; x > 0; x-=(x&-x)) zbr+=f[x];
    return zbr;
}

void update (int x, int val) {
    for (; x < N; x+=(x&-x)) f[x]+=val;
return;
}

int kol (int x) {
    if (!x) return 0;
    lli zbr=0;
    for (; x > 0; x-=(x&-x)) zbr+=active[x];
    return zbr;
}

void update_active (int x, int val) {
    for (; x < N; x+=(x&-x)) active[x]+=val;
return;
}

void sazmi () {
    sort (v.begin(), v.end());
    for (int i = 1; i <= m; i++) {
        b[i] = lower_bound(v.begin(), v.end(), b[i])-v.begin()+1;
        if (i <= n) poc.push_back(b[i]);
    }
    sort (poc.begin(), poc.end());
    for (int i = 1; i <= n; i++) {
        lli val = lower_bound(poc.begin(), poc.end(), b[i])-poc.begin()+1;
        if (i==1) hesh=val;
        else hesh=(hesh*B%MOD+val)%MOD;
        update(b[i], divide(1, pot[upd]));
        upd++;
        update_active(b[i], 1);
    }
return;
}

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> d;
        a[d]=i;
    }
    br=m-1;
    upd=0;
    pot[0]=1;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        v.push_back(b[i]);
        pot[i]=(pot[i-1]*B)%MOD;
    }
    hesh=0;
    sazmi ();
    //for (int i = 1; i <= n; i++) cout << a[i] << " ";
    for (int i = 1; i <= n; i++) {
        if (i==1) sub=a[i];
        else sub=((sub*B+a[i])%MOD)%MOD;
    }
    if (sub == hesh) sol.push_back(1);
    //cout << sub << " " << hesh << endl;
    for (int i = n+1; i <= m; i++) {
        lli dod = sum(N-5)-sum(b[i]);
        dod=(dod*pot[upd-1]%MOD);
        lli kolikoManjih = kol(b[i]);
        hesh = ((hesh+dod)*B%MOD+kolikoManjih+1)%MOD;
        /*for (int j = 1; j < N; j++) {
            if (sum(j)-sum(j-1)) cout << j << " " << (sum(j)-sum(j-1))*pot[upd-1]%MOD << endl;
        }
        cout << upd << " " << sum(N-5)*pot[upd-1]%MOD << endl;*/
        update_active(b[i], 1);
        update(b[i], divide(1, pot[upd]));
        upd++;

        int last = i-n;
        kolikoManjih = kol(b[last]);
        hesh = (hesh-kolikoManjih*pot[n]%MOD)%MOD;
        lli makni = sum(b[last])-sum(b[last]-1);
        update (b[last], -makni);
        update_active (b[last], -1);
        dod = sum(N-5)-sum(b[last]);
        dod = (dod*pot[upd-1])%MOD;
        hesh = ((hesh-dod)%MOD+MOD)%MOD;
        if (hesh==sub) sol.push_back(i-n+1);
    }
    cout << sol.size() << "\n";
    for (int i = 0; i < sol.size(); i++) cout << sol[i] << " ";
return;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	solve();

return 0;
}
/*
5 9
1 4 2 3 5
1 4 5 2 6 8 11 7 16

5 8
1 4 2 3 5
1 4 5 2 6 8 7 11
*/

Compilation message (stderr)

mat.cpp: In function 'void solve()':
mat.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < sol.size(); i++) cout << sol[i] << " ";
      |                     ~~^~~~~~~~~~~~

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