oj.uz

Submission #244305

# Submission time Handle Problem Language Result Execution time Memory
244305 2020-07-03T15:02:22 Z TadijaSebez Matching (CEOI11_mat) C++11
100 / 100
 894 ms 44268 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1000050;
const int base=7777777;
const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
int powmod(int x,int k){
	int ans=1;
	for(;k;k>>=1,x=mul(x,x))if(k&1)ans=mul(ans,x);
	return ans;
}
int inv(int x){return powmod(x,mod-2);}
int dvd(int x,int y){return mul(x,inv(y));}
int pw[N];

/*const int M=2*N;
int ls[M],rs[M],tsz,root,sum[M],num[M],lzy[M];
void Build(int&c,int ss,int se){
	c=++tsz;lzy[c]=1;
	if(ss==se)return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void push(int c){
	if(lzy[c]!=1){
		sum[ls[c]]=mul(sum[ls[c]],lzy[c]);
		sum[rs[c]]=mul(sum[rs[c]],lzy[c]);
		lzy[ls[c]]=mul(lzy[ls[c]],lzy[c]);
		lzy[rs[c]]=mul(lzy[rs[c]],lzy[c]);
		lzy[c]=1;
	}
}
void Set(int c,int ss,int se,int qi,int f,int x){
	if(ss==se){
		sum[c]=x;
		num[c]=f;
		return;
	}
	push(c);
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ss,mid,qi,f,x);
	else Set(rs[c],mid+1,se,qi,f,x);
	sum[c]=add(sum[ls[c]],sum[rs[c]]);
	num[c]=num[ls[c]]+num[rs[c]];
}
void Mul(int c,int ss,int se,int qs,int qe,int x){
	if(qs>qe||qs>se||ss>qe)return;
	if(qs<=ss&&qe>=se){lzy[c]=mul(lzy[c],x);sum[c]=mul(sum[c],x);return;}
	int mid=ss+se>>1;
	push(c);
	Mul(ls[c],ss,mid,qs,qe,x);
	Mul(rs[c],mid+1,se,qs,qe,x);
	sum[c]=add(sum[ls[c]],sum[rs[c]]);
	num[c]=num[ls[c]]+num[rs[c]];
}
int Get(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return 0;
	if(qs<=ss&&qe>=se)return sum[c];
	int mid=ss+se>>1;
	push(c);
	return add(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
int GetCnt(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return 0;
	if(qs<=ss&&qe>=se)return num[c];
	int mid=ss+se>>1;
	push(c);
	return GetCnt(ls[c],ss,mid,qs,qe)+GetCnt(rs[c],mid+1,se,qs,qe);
}*/

int leaf[N],has[N],ml=1,dv=1,root,ibase;
void Build(int&c,int ss,int se){}
void Set(int c,int ss,int se,int qi,int f,int x){
	x=mul(x,ml);
	for(int i=qi;i<N;i+=i&-i){
		leaf[i]=add(leaf[i],x);
		has[i]+=f?1:-1;
	}
}
void Mul(int c,int ss,int se,int qs,int qe,int x){
	ml=mul(ml,base);
	dv=mul(dv,ibase);
}
int Get(int c,int ss,int se,int qs,int qe){
	int ans=0;
	for(int i=qe;i;i-=i&-i)ans=add(ans,leaf[i]);
	for(int i=qs-1;i;i-=i&-i)ans=sub(ans,leaf[i]);
	return mul(ans,dv);
}
int GetCnt(int c,int ss,int se,int qs,int qe){
	int ans=0;
	for(int i=qe;i;i-=i&-i)ans+=has[i];
	for(int i=qs-1;i;i-=i&-i)ans-=has[i];
	return ans;
}

//int leaf[N],has[N];
void Ins(int x,int f){
	Set(root,1,N-1,x,1,f);
	//has[x]=1;
	//leaf[x]=f;
}
void Ers(int x,int f){
	Set(root,1,N-1,x,0,sub(0,Get(root,1,N-1,x,x)));
	//has[x]=0;
	//leaf[x]=f;
}
void Dvd(int l,int r,int f){
	//f=inv(f);
	Mul(root,1,N-1,l,r,f);
	//for(int i=l;i<=r;i++)leaf[i]=mul(leaf[i],f);
}
int Get(int l,int r){
	return Get(root,1,N-1,l,r);
	//int ans=0;
	//for(int i=l;i<=r;i++)ans=add(ans,leaf[i]);
	//return ans;
}
int GetCnt(int l,int r){
	return GetCnt(root,1,N-1,l,r);
	//int ans=0;
	//for(int i=l;i<=r;i++)ans+=has[i];
	//return ans;
}

int hsh,cnt;
void Add(int x){
	hsh=add(hsh,Get(x+1,N-1));
	Ins(x,pw[cnt]);
	hsh=add(hsh,mul(GetCnt(1,x),pw[cnt]));
	cnt++;
}
void Del(int x){
	int tmp=GetCnt(1,x);
	hsh=sub(hsh,tmp);
	Ers(x,0);
	hsh=mul(hsh,ibase);
	Dvd(1,N-1,base);
	hsh=sub(hsh,Get(x+1,N-1));
	cnt--;
}
int a[N],b[N],p[N];
int main(){
	pw[0]=1;for(int i=1;i<N;i++)pw[i]=mul(pw[i-1],base);ibase=inv(base);
	Build(root,1,N-1);
	int n,m;scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),p[a[i]]=i;
	int goal=0;
	for(int i=n;i>=1;i--)goal=add(mul(goal,base),p[i]);
	vector<int> all;
	for(int i=1;i<=m;i++)scanf("%i",&b[i]),all.pb(b[i]);
	sort(all.begin(),all.end());
	for(int i=1;i<=m;i++)b[i]=lower_bound(all.begin(),all.end(),b[i])-all.begin()+1;

	for(int i=1;i<n;i++)Add(b[i]);
	vector<int> ans;
	for(int i=n;i<=m;i++){
		Add(b[i]);
		//printf("%i %i\n",hsh,goal);
		if(hsh==goal)ans.pb(i-n+1);
		Del(b[i-n+1]);
	}
	printf("%i\n",ans.size());
	for(int i:ans)printf("%i ",i);
	return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:168:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%i\n",ans.size());
                ~~~~~~~~~~^
mat.cpp:151:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m;scanf("%i %i",&n,&m);
          ~~~~~^~~~~~~~~~~~~~~
mat.cpp:152:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&a[i]),p[a[i]]=i;
                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~
mat.cpp:156:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++)scanf("%i",&b[i]),all.pb(b[i]);
                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4352 KB Output is correct
2 Correct 12 ms 4352 KB Output is correct
3 Correct 12 ms 4352 KB Output is correct
4 Correct 11 ms 4352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4352 KB Output is correct
2 Correct 13 ms 4352 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4992 KB Output is correct
2 Correct 21 ms 4864 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4992 KB Output is correct
2 Correct 21 ms 4992 KB Output is correct
3 Correct 13 ms 4480 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9068 KB Output is correct
2 Correct 105 ms 8764 KB Output is correct
3 Correct 151 ms 10224 KB Output is correct
4 Correct 147 ms 10220 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 9864 KB Output is correct
2 Correct 149 ms 9580 KB Output is correct
3 Correct 120 ms 9836 KB Output is correct
4 Correct 113 ms 10984 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 10088 KB Output is correct
2 Correct 107 ms 9448 KB Output is correct
3 Correct 130 ms 9548 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 32604 KB Output is correct
2 Correct 894 ms 44268 KB Output is correct
3 Correct 524 ms 24540 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 32136 KB Output is correct
2 Correct 825 ms 26844 KB Output is correct
3 Correct 837 ms 40804 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 29788 KB Output is correct
2 Correct 527 ms 37588 KB Output is correct
3 Correct 674 ms 30300 KB Output is correct
4 Correct 517 ms 42460 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 30508 KB Output is correct
2 Correct 669 ms 30812 KB Output is correct
3 Correct 251 ms 17380 KB Output is correct
4 Correct 624 ms 42240 KB Output is correct