Submission #747835

#	Time	Username	Problem	Language	Result	Execution time	Memory
747835		Hyojin	Matching (CEOI11_mat)	C++17	100 / 100	1595 ms	53556 KiB

mat

#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define deb(x) cerr << #x << ' ' << x << '\n'
const int MOD=1e9+7;
const int N=1e6+5;
void setIO(const string &NAME)
{
	if (NAME.size())
	{
		freopen((NAME+".inp").c_str(),"r",stdin);
		freopen((NAME+".out").c_str(),"w",stdout);
	}
}
int mul(int a,int b){return (1ll*a*b)%MOD;}
int add(int a,int b){return (a+b)%MOD;}
int sub(int a,int b){return (a-b+MOD)%MOD;}
int n,m,b[N],hashA,sum1[N],Pow[N],st[N*4],cnt[N*4],lazy[N*4];
int base;
vector<int>f;
void down(int id)
{	
	if (lazy[id]!=0)
	{
		int x=lazy[id];
		st[id<<1]=sub(st[id<<1],mul(x,sum1[cnt[id<<1]]));
		st[id<<1|1]=sub(st[id<<1|1],mul(x,sum1[cnt[id<<1|1]]));
		lazy[id<<1]+=x;
		lazy[id<<1|1]+=x;
		lazy[id]=0;
	}
}
void update(int id,int l,int r,int x,int val)
{
	if (x<l||r<x) return;
	if (l==r)
	{
		if (val!=-1) 
		{
			st[id]=val;
			cnt[id]=1;
		}
		else
		{
			cnt[id]=0;
			st[id]=0;
		}
		return;
	}
	down(id);
	int mid=l+r>>1;
	update(id<<1,l,mid,x,val);
	update(id<<1|1,mid+1,r,x,val);
	st[id]=add(st[id<<1|1],mul(st[id<<1],Pow[cnt[id<<1|1]]));
	cnt[id]=cnt[id<<1]+cnt[id<<1|1];
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifdef izumiShiho
    	setIO("input");
	#endif //izumiShiho
    cin>>n>>m;
    base=n+5;
    Pow[0]=1;
    sum1[0]=0;
    for (int i=1;i<=n;i++)
    {
    	Pow[i]=mul(Pow[i-1],base);
    	sum1[i]=add(mul(sum1[i-1],base),1);
    	int x;
    	cin>>x;
    	hashA=add(mul(hashA,base),x);
    }
    for (int i=1;i<=m;i++)
    {
    	cin>>b[i];
    	f.pb(b[i]);
    }
    sort(all(f));
    for (int i=1;i<=m;i++) b[i]=lower_bound(all(f),b[i])-f.begin()+1;
    for (int i=1;i<=n;i++) update(1,1,m,b[i],i);
    vector<int>ans;
    if (hashA==st[1]) ans.pb(1);
    for (int i=n+1;i<=m;i++)
    {
    	update(1,1,m,b[i-n],-1);
    	lazy[1]++;
    	sub(st[1],sum1[n]);
    	update(1,1,m,b[i],n);
    	if (st[1]==hashA) ans.pb(i-n+1);
    }
   	cout<<ans.size()<<"\n";
   	for (int x:ans) cout<<x<<' ';
	return 0;
}

Compilation message (stderr)

mat.cpp: In function 'void update(int, int, int, int, int)':
mat.cpp:59:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |  int mid=l+r>>1;
      |          ~^~
mat.cpp: In function 'void setIO(const string&)':
mat.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen((NAME+".inp").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   freopen((NAME+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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