Submission #840291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840291	2023-08-31T09:30:37 Z	Dec0Dedd	Matching (CEOI11_mat)	C++14	63 / 100	554 ms	65536 KB

#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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	8084 KB	Output is correct
2	Correct	7 ms	8136 KB	Output is correct
3	Correct	7 ms	8156 KB	Output is correct
4	Correct	7 ms	8148 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8520 KB	Output is correct
2	Correct	9 ms	8396 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	14468 KB	Output is correct
2	Correct	33 ms	14164 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	14548 KB	Output is correct
2	Correct	44 ms	14512 KB	Output is correct
3	Correct	14 ms	9036 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	60488 KB	Output is correct
2	Correct	371 ms	61972 KB	Output is correct
3	Correct	554 ms	64360 KB	Output is correct
4	Correct	498 ms	64352 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	365 ms	62920 KB	Output is correct
2	Correct	553 ms	63496 KB	Output is correct
3	Correct	379 ms	63360 KB	Output is correct
4	Correct	386 ms	64780 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	363 ms	62648 KB	Output is correct
2	Correct	352 ms	63332 KB	Output is correct
3	Correct	399 ms	63248 KB	Output is correct

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	280 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	288 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	320 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	317 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #840291

Compilation message