Submission #482027

#	Time	Username	Problem	Language	Result	Execution time	Memory
482027		Bench0310	Matching (CEOI11_mat)	C++17	100 / 100	921 ms	60884 KiB

mat

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1000000;
ll tree[2097149+1];
int sz[2097149+1];
const ll p=1000037;
const ll mod=1000000007;
ll add(ll a,ll b){return (a+b)%mod;}
ll mul(ll a,ll b){return (a*b)%mod;}
ll 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);
    ll r=0;
    ll 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]);
    }
    vector<array<int,2>> h(n);
    for(int i=0;i<n;i++)
    {
        cin >> h[i][0];
        h[i][1]=i+1;
    }
    sort(h.begin(),h.end());
    vector<int> pos(n+1,0);
    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 / 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: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10