oj.uz

Submission #747835

# Submission time Handle Problem Language Result Execution time Memory
747835 2023-05-24T21:16:33 Z Hyojin Matching (CEOI11_mat) C++17
100 / 100
 1595 ms 53556 KB 
#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

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1600 KB Output is correct
2 Correct 14 ms 1492 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1600 KB Output is correct
2 Correct 17 ms 1584 KB Output is correct
3 Correct 3 ms 468 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 9816 KB Output is correct
2 Correct 185 ms 9520 KB Output is correct
3 Correct 225 ms 10800 KB Output is correct
4 Correct 245 ms 10796 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 10424 KB Output is correct
2 Correct 295 ms 10188 KB Output is correct
3 Correct 193 ms 10488 KB Output is correct
4 Correct 179 ms 11516 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 10660 KB Output is correct
2 Correct 177 ms 10036 KB Output is correct
3 Correct 233 ms 10180 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1129 ms 45472 KB Output is correct
2 Correct 950 ms 48876 KB Output is correct
3 Correct 1149 ms 39192 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 45172 KB Output is correct
2 Correct 1595 ms 39604 KB Output is correct
3 Correct 928 ms 53556 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1205 ms 42684 KB Output is correct
2 Correct 1024 ms 50568 KB Output is correct
3 Correct 1354 ms 43200 KB Output is correct
4 Correct 575 ms 47040 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 43400 KB Output is correct
2 Correct 1297 ms 43616 KB Output is correct
3 Correct 524 ms 21680 KB Output is correct
4 Correct 709 ms 48844 KB Output is correct