Submission #482028

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
482028	2021-10-22T16:52:06 Z	Bench0310	Matching (CEOI11_mat)	C++17	100 / 100	939 ms	39352 KB

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1000000;
int tree[2097149+1];
int sz[2097149+1];
const int p=1000037;
const int mod=1000000007;
int add(int a,int b){return a+b-(a+b>=mod?mod:0);}
int mul(int a,int b){return (ll(a)*b)%mod;}
int pw[N+1];

void update(int idx,int l,int r,int pos,int val,int s)
{
    if(l==r)
    {
        tree[idx]=val;
        sz[idx]=s;
    }
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,val,s);
        else update(2*idx+1,m+1,r,pos,val,s);
        tree[idx]=add(mul(pw[sz[2*idx+1]],tree[2*idx]),tree[2*idx+1]);
        sz[idx]=sz[2*idx]+sz[2*idx+1];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> m >> n;
    pw[0]=1;
    for(int i=1;i<=m;i++) pw[i]=mul(pw[i-1],p);
    int r=0;
    int s=0;
    for(int i=1;i<=m;i++)
    {
        int b;
        cin >> b;
        r=add(mul(p,r),b);
        s=add(s,pw[i-1]);
    }
    array<int,2> h[n];
    for(int i=0;i<n;i++)
    {
        cin >> h[i][0];
        h[i][1]=i+1;
    }
    sort(h,h+n);
    int pos[n+1];
    for(int i=0;i<n;i++) pos[h[i][1]]=i+1;
    auto add_t=[&](int i){update(1,1,n,pos[i],i,1);};
    auto rm_t=[&](int i){update(1,1,n,pos[i],0,0);};
    for(int i=1;i<m;i++) add_t(i);
    vector<int> res;
    for(int i=m;i<=n;i++)
    {
        add_t(i);
        if(tree[1]==r) res.push_back(i-m+1);
        rm_t(i-m+1);
        r=add(r,s);
    }
    cout << res.size() << "\n";
    for(int a:res) cout << a << " ";
    cout << "\n";
    return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	972 KB	Output is correct
2	Correct	10 ms	972 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1100 KB	Output is correct
2	Correct	11 ms	1100 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	6620 KB	Output is correct
2	Correct	123 ms	6672 KB	Output is correct
3	Correct	158 ms	6984 KB	Output is correct
4	Correct	149 ms	6940 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	7304 KB	Output is correct
2	Correct	183 ms	6788 KB	Output is correct
3	Correct	128 ms	7160 KB	Output is correct
4	Correct	134 ms	8912 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	121 ms	7292 KB	Output is correct
2	Correct	123 ms	6852 KB	Output is correct
3	Correct	135 ms	6812 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	738 ms	30124 KB	Output is correct
2	Correct	723 ms	32360 KB	Output is correct
3	Correct	714 ms	25948 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	673 ms	29056 KB	Output is correct
2	Correct	939 ms	28456 KB	Output is correct
3	Correct	735 ms	32220 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	763 ms	29560 KB	Output is correct
2	Correct	739 ms	39352 KB	Output is correct
3	Correct	833 ms	28484 KB	Output is correct
4	Correct	516 ms	32396 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	732 ms	30040 KB	Output is correct
2	Correct	789 ms	28940 KB	Output is correct
3	Correct	318 ms	14736 KB	Output is correct
4	Correct	586 ms	32068 KB	Output is correct

Submission #482028

Compilation message