Submission #840306

#	Time	Username	Problem	Language	Result	Execution time	Memory
840306		Dec0Dedd	Matching (CEOI11_mat)	C++14	63 / 100	424 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;
    int cnt; 
    V() {sum=pwsum=cnt=0;};
};
 
struct segtree {
    vector<V> t;
    vector<int> 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+=1ll*t[2*v].pwsum*lz[v];
        t[2*v+1].sum+=1ll*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]);
    }
};
 
int 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);
}
 
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;
 
    vector<int> v;
    for (int i=1; i<=n; ++i) cin>>tmp[i], s[tmp[i]]=i;
    for (int i=1; i<=m; ++i) {
        cin>>a[i];
        v.push_back(a[i]);
    } sort(v.begin(), v.end());
    
    for (int i=1; i<=m; ++i) a[i]=(lower_bound(v.begin(), v.end(), a[i])-v.begin())+1;
 
    p[0]=1, p[1]=P;
    for (int i=2; i<N; ++i) p[i]=(1ll*p[i-1]*P)%MOD;
 
    t.init(m+1);
    ll h=0;
    for (int i=1; i<=n; ++i) (h+=1ll*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