Submission #545430

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545430	2022-04-04T13:53:22 Z	nishkarsh	Matching (CEOI11_mat)	C++14	100 / 100	674 ms	40040 KB

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 1e6+10;
const int mod = 1e9+7;
int Z_func[upperlimit];
int arr[upperlimit];
int fenwick[upperlimit];
int a[upperlimit];
struct indval{
	int ind,val;
};
bool cmp1(indval a,indval b){
	return(a.val<b.val);
}
bool cmp2(indval a,indval b){
	return(a.ind<b.ind);
}
indval b[upperlimit];
int N=upperlimit-1;
int lsb(int pos){
	return (pos&(-pos));
}
void update(int pos,int val){
	while(pos <= N){
		fenwick[pos]+=val;
		pos+=lsb(pos);
	}
}
int query(int pos){
	int ans=0;
	while(pos>0){
		ans+=fenwick[pos];
		pos-=lsb(pos);
	}
	return ans;
}
int main(){
	int n,m,x;
	sd(n);sd(m);
	for(int i = 1; i <= n; i++){
		sd(x);
		a[x]=i;
	}
	for(int i = 1; i <= m; i++){
		sd(b[i].val);
		b[i].ind=i;
	}
	sort(b+1,b+m+1,cmp1);
	for(int i = 1; i <= m; i++) b[i].val=i;
	sort(b+1,b+m+1,cmp2);
	int cur=0,p=2,curr_value;
	Z_func[1]=0;
	N=max(n,m);
	for(int i = 1; i <= n; i++){
		update(a[i],1);
		arr[i] = query(a[i]);
//		cout << arr[i] << " ";
	}
	for(int i = 1; i <= n; i++) update(a[i],-1);
	for(int i = 2; i <= n; i++){
		update(a[i],1);
		curr_value = query(a[i]);
		while(curr_value!=arr[cur+1]){
			if(cur==0) break;
			cur = Z_func[cur];
			while(p < i-cur){
				update(a[p],-1);
				p++;
			}
			curr_value = query(a[i]);
		}
		if(arr[cur+1]==curr_value) cur++;
		Z_func[i]=cur;
	}
	while(p<=n){
		update(a[p],-1);
		p++;
	}
	arr[n+1]=0;
	cur=0;
	p=1;
	int cnt = 0;
	vi ans;
	for(int i = 1; i <= m; i++){
		update(b[i].val,1);
		curr_value = query(b[i].val);
		while(curr_value!=arr[cur+1]){
			if(cur==0) break;
			cur = Z_func[cur];
			while(p < i-cur){
				update(b[p].val,-1);
				p++;
			}
			curr_value = query(b[i].val);
		}
		if(arr[cur+1]==curr_value) cur++;
		if(cur==n){
			cnt++;
			ans.pb(i+1-n);
		}
	}
	pdn(cnt);
	for(int i = 0; i < cnt; i++) pds(ans[i]);
	return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:74:2: note: in expansion of macro 'sd'
   74 |  sd(n);sd(m);
      |  ^~
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:74:8: note: in expansion of macro 'sd'
   74 |  sd(n);sd(m);
      |        ^~
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:76:3: note: in expansion of macro 'sd'
   76 |   sd(x);
      |   ^~
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:80:3: note: in expansion of macro 'sd'
   80 |   sd(b[i].val);
      |   ^~

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	316 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	8 ms	724 KB	Output is correct
2	Correct	7 ms	708 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	724 KB	Output is correct
2	Correct	7 ms	708 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	4264 KB	Output is correct
2	Correct	54 ms	3976 KB	Output is correct
3	Correct	92 ms	5412 KB	Output is correct
4	Correct	103 ms	5440 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	5220 KB	Output is correct
2	Correct	77 ms	4680 KB	Output is correct
3	Correct	69 ms	5184 KB	Output is correct
4	Correct	67 ms	6076 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	5252 KB	Output is correct
2	Correct	62 ms	4776 KB	Output is correct
3	Correct	71 ms	4808 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	424 ms	25500 KB	Output is correct
2	Correct	674 ms	40040 KB	Output is correct
3	Correct	301 ms	17388 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	412 ms	25264 KB	Output is correct
2	Correct	409 ms	18768 KB	Output is correct
3	Correct	668 ms	36236 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	424 ms	21564 KB	Output is correct
2	Correct	366 ms	29744 KB	Output is correct
3	Correct	426 ms	22524 KB	Output is correct
4	Correct	540 ms	38168 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	366 ms	22420 KB	Output is correct
2	Correct	398 ms	23000 KB	Output is correct
3	Correct	157 ms	11460 KB	Output is correct
4	Correct	558 ms	37500 KB	Output is correct