Submission #1288216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288216		LmaoLmao	Matching (CEOI11_mat)	C++20	100 / 100	352 ms	62248 KiB

mat

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define name "MOHINHGIA"
using namespace std;

using ii = pair<signed,signed>;
using aa = array<int,4>;
const int N=1e6+5;
const int MOD=1e9+7;
const int base=1e6+7;

void add(int &a,int b) {
    a+=b;
    if(a<0) a+=MOD;
    if(a>=MOD) a-=MOD;
    //return a;
}
void mul(int &a,int b) {
    a*=b;
    a%=MOD;
}

int bp(int a,int b) {
    int res=1;
    while(b>0) {
        if(b&1) mul(res,a);
        mul(a,a);
        b>>=1;
    }
    return res;
}

struct SMT {
    int F[N*2];
    int a[N];
    void update(int pos,int val) {
        int x=-a[pos]+val;
        if(x<0) x+=MOD;
        a[pos]=val;
        for(int i=pos;i<N;i+=i & -i) {
            add(F[i],x);
        }
    }
    int GET(int pos) {
        int res=0;
        for(int i=pos;i>0;i-=i & -i) {
            add(res,F[i]);
        }
        return res;
    }
    int get(int l,int r)
    {
        return (GET(r)-GET(l-1)+MOD)%MOD;
    }
} S;

struct BIT {
    int F[N];
    void update(int pos,int val) {
        for(int i=pos;i<N;i+=i & -i) {
            F[i]+=val;
        }
    }
    int get(int pos) {
        int res=0;
        for(int i=pos;i>0;i-=i & -i) {
            res+=F[i];
        }
        return res;
    }

} F;

signed a[N];
ii nen[N];
signed mp[N];
int binpow[N];
int inv[N];
int pre[N];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,m;
    cin >> n >> m;
    int huyhau=0;
    binpow[0]=pre[0]=1;
    vector<ii> sigma;
    int sum=0;
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        mp[x]=i;
    }
    for(int i=1;i<=n;i++) {
        mul(huyhau,base);
        add(huyhau,mp[i]);
    }
    for(int i=1;i<=m;i++) {
        binpow[i]=binpow[i-1]*base%MOD;
        cin >> a[i];
        nen[i]={a[i],i};
    }
    inv[m]=bp(binpow[m],MOD-2);
    for(int i=m-1;i>=0;i--) {
        inv[i]=inv[i+1]*base%MOD;
    }
    vector<signed> ans;
    sort(nen+1,nen+1+m);
    if(m<n) {
        cout << 0;
        return 0;
    }
    for(int i=1;i<=m;i++) {
        a[nen[i].se]=i;
    }
    int cur=0;
    for(int i=1;i<=n;i++) {
        F.update(a[i],1);
    }
    for(int i=1;i<=n;i++) {
        cur=cur+F.get(a[i])*binpow[m-i];
        cur%=MOD;
        S.update(a[i],binpow[m-i]);
        //cout << cur << ' ';
    }
    //cout << endl;
    if(cur*inv[m-n]%MOD==huyhau) {
        ans.push_back(1);
    }
    for(int i=n+1;i<=m;i++) {
        if(a[i-n]!=m)add(cur,-S.get(a[i-n]+1,m));
        add(cur,(-F.get(a[i-n]))*binpow[m-(i-n)]%MOD);
        S.update(a[i-n],0);
        F.update(a[i-n],-1);

        S.update(a[i],binpow[m-i]);
        F.update(a[i],1);
        add(cur,F.get(a[i])*binpow[m-i]%MOD);
        if(a[i]!=m) add(cur,S.get(a[i]+1,m));

        cur%=MOD;
        if(cur*inv[m-i]%MOD==huyhau) ans.push_back(i-n+1);
    }
    cout << ans.size() << endl;
    for(int x:ans) cout << x << ' ';
    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