Submission #840305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840305	2023-08-31T09:41:31 Z	Dec0Dedd	Matching (CEOI11_mat)	C++14	63 / 100	438 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;
    int 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);
}
 
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]=(p[i-1]*P)%MOD;
 
    t.init(m+1);
    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	8148 KB	Output is correct
2	Correct	7 ms	8148 KB	Output is correct
3	Correct	7 ms	8148 KB	Output is correct
4	Correct	8 ms	8248 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	8404 KB	Output is correct
2	Correct	8 ms	8276 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	12628 KB	Output is correct
2	Correct	30 ms	12628 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	12744 KB	Output is correct
2	Correct	33 ms	12756 KB	Output is correct
3	Correct	11 ms	8660 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	282 ms	43892 KB	Output is correct
2	Correct	306 ms	43460 KB	Output is correct
3	Correct	396 ms	44208 KB	Output is correct
4	Correct	398 ms	44368 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	305 ms	44448 KB	Output is correct
2	Correct	438 ms	43568 KB	Output is correct
3	Correct	326 ms	43980 KB	Output is correct
4	Correct	323 ms	45452 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	297 ms	44576 KB	Output is correct
2	Correct	307 ms	44176 KB	Output is correct
3	Correct	333 ms	43896 KB	Output is correct

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	274 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	257 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	235 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	226 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #840305

Compilation message