제출 #840291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
840291		Dec0Dedd	Matching (CEOI11_mat)	C++14	63 / 100	554 ms	65536 KiB

mat

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 1e6+10;
const ll P = 2137;
const int MOD = 1e9+7;

struct V {
    ll sum, pwsum, cnt; 
    V() {sum=pwsum=cnt=0;};
};

struct segtree {
    vector<V> t;
    vector<ll> lz;

    void init(int k) {
        int sz=1;
        while (sz < 4*k) sz*=2;
        t.resize(sz), lz.resize(sz);
    }

    void push(int v) {
        lz[2*v]+=lz[v], lz[2*v+1]+=lz[v];
        t[2*v].sum+=t[2*v].pwsum*lz[v];
        t[2*v+1].sum+=t[2*v+1].pwsum*lz[v];
        lz[v]=0;
    }

    V mrg(V a, V b) {
        V res;
        res.sum=(a.sum+b.sum)%MOD, res.cnt=(a.cnt+b.cnt)%MOD, res.pwsum=(a.pwsum+b.pwsum)%MOD;
        return res;
    }

    void upd(int v, int l, int r, int ql, int qr, int val) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            t[v].sum+=val*t[v].pwsum, lz[v]+=val;
            if (l < r) push(v);
            return;
        } int m=(l+r)/2; push(v);
        upd(2*v, l, m, ql, qr, val), upd(2*v+1, m+1, r, ql, qr, val);
        t[v]=mrg(t[2*v], t[2*v+1]);
    }

    V que(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return V();
        if (l >= ql && r <= qr) return t[v];
        int m=(l+r)/2; push(v);
        return mrg(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
    }

    void st(int v, int l, int r, int p, V x) {
        if (l == r) {
            t[v]=x;
            return;
        } int m=(l+r)/2; push(v);
        if (p <= m) st(2*v, l, m, p, x);
        else st(2*v+1, m+1, r, p, x);
        t[v]=mrg(t[2*v], t[2*v+1]);
    }
};

ll tmp[N], s[N], a[N], p[N], n, m;

ll bpw(ll x, ll n) {
    if (n == 0) return 1;
    ll c=bpw(x, n/2);
    (c=c*c)%=MOD;
    if (n&1) return (c*x)%MOD;
    return c;
}

ll inv(ll x) {
    return bpw(x, MOD-2);
}

set<int> ss;
map<int, int> sc;

segtree t;

void add(int i) {
    ll z=t.que(1, 1, m, 1, a[i]-1).cnt+1;
    V x; x.cnt=1, x.pwsum=p[i], x.sum=p[i]*z;
    t.upd(1, 1, m, a[i], m, 1); t.st(1, 1, m, a[i], x);
}

void rem(int i) {
    t.upd(1, 1, m, a[i]+1, m, -1);
    t.st(1, 1, m, a[i], V());
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for (int i=1; i<=n; ++i) cin>>tmp[i], s[tmp[i]]=i;
    for (int i=1; i<=m; ++i) {
        cin>>a[i];
        ss.insert(a[i]);
    }

    int i=1;
    for (auto u : ss) sc[u]=i++;
    for (int i=1; i<=m; ++i) a[i]=sc[a[i]];

    p[0]=1, p[1]=P;
    for (int i=2; i<N; ++i) p[i]=(p[i-1]*P)%MOD;

    t.init(m+10);
    ll h=0;
    for (int i=1; i<=n; ++i) (h+=s[i]*p[i])%=MOD;
    for (int i=1; i<=n; ++i) add(i);

    vector<int> ans;
    for (int i=n; i<=m; ++i) {
        ll hp=(t.t[1].sum*inv(p[i-n]))%MOD;
        (hp+=MOD)%=MOD;
        if (h == hp) ans.push_back(i-n+1);
        if (i+1 <= m) rem(i-n+1), add(i+1);
    }

    cout<<ans.size()<<"\n";
    for (auto u : ans) cout<<u<<" ";
    cout<<"\n";
}

• 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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10