Submission #827081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
827081	2023-08-16T08:36:28 Z	sentheta	Lottery (CEOI18_lot)	C++17	100 / 100	355 ms	12384 KB

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}










const int N = 1e4+5;
const int Q = 105;

int n, len, q;
int a[N];

// point to next possible query
int ptr[N];
int find(int x){
	if(ptr[x]==x) return x;
	return ptr[x] = find(ptr[x]);
}

int qrys[Q];
V<int> ans[N];


void solve(){
	
	cin >> n >> len;
	
	rep(i,0,n){
		cin >> a[i];
	}
	
	rep(i,0,N) ptr[i] = i+1;
	ptr[N-1] = N-1;
	
	cin >> q;
	rep(i,0,q){
		cin >> qrys[i];
		
		ptr[qrys[i]] = qrys[i];
	}
	rep(i,0,N) if(ptr[i]==i){
		ans[i] = V<int>(n-len+1);
	}
	
	
	// consider all shifts	
	for(int sh=1; sh+len-1<n; sh++){
		int i=0, j=sh;
		
		// compare first
		int diff = 0;
		rep(k,0,len){
			diff += a[i+k]!=a[j+k];
		}
		ans[find(diff)][i]++;
		ans[find(diff)][j]++;
		
		// continue comparison
		i++; j++;
		for(; j+len-1<n; i++,j++){
			diff -= a[i-1]!=a[j-1];
			diff += a[i+len-1]!=a[j+len-1];
			
			// {
			// 	int tmp=0;
			// 	rep(k,0,len){
			// 		tmp += a[i+k]!=a[j+k];
			// 	}
			// 	assert(tmp==diff);
			// }

			ans[find(diff)][i]++;
			ans[find(diff)][j]++;
		}
	}
	
	
	
	// cumulative sum
	int prv = -1;
	rep(i,0,N) if(!ans[i].empty()){
		if(prv==-1){
			prv = i; continue;
		}
		rep(j,0,n-len+1){
			ans[i][j] += ans[prv][j];
		}
		prv = i;
	}
	
	
	rep(i,0,q){
		for(int x : ans[qrys[i]]){
			cout << x << " ";
		}
		cout << nl;
	}
	
	
	
}

Subtask #1
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	724 KB	Output is correct
3	Correct	1 ms	568 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	724 KB	Output is correct
12	Correct	1 ms	596 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	724 KB	Output is correct
3	Correct	1 ms	568 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	724 KB	Output is correct
12	Correct	1 ms	596 KB	Output is correct
13	Correct	9 ms	724 KB	Output is correct
14	Correct	6 ms	852 KB	Output is correct
15	Correct	6 ms	852 KB	Output is correct
16	Correct	10 ms	1108 KB	Output is correct
17	Correct	9 ms	1076 KB	Output is correct
18	Correct	12 ms	1072 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	277 ms	1000 KB	Output is correct
2	Correct	223 ms	1000 KB	Output is correct
3	Correct	230 ms	1100 KB	Output is correct
4	Correct	235 ms	1076 KB	Output is correct
5	Correct	84 ms	940 KB	Output is correct
6	Correct	190 ms	1064 KB	Output is correct
7	Correct	130 ms	880 KB	Output is correct
8	Correct	107 ms	916 KB	Output is correct
9	Correct	224 ms	1068 KB	Output is correct
10	Correct	220 ms	1068 KB	Output is correct
11	Correct	11 ms	724 KB	Output is correct
12	Correct	125 ms	988 KB	Output is correct
13	Correct	93 ms	976 KB	Output is correct
14	Correct	93 ms	980 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	277 ms	1000 KB	Output is correct
2	Correct	223 ms	1000 KB	Output is correct
3	Correct	230 ms	1100 KB	Output is correct
4	Correct	235 ms	1076 KB	Output is correct
5	Correct	84 ms	940 KB	Output is correct
6	Correct	190 ms	1064 KB	Output is correct
7	Correct	130 ms	880 KB	Output is correct
8	Correct	107 ms	916 KB	Output is correct
9	Correct	224 ms	1068 KB	Output is correct
10	Correct	220 ms	1068 KB	Output is correct
11	Correct	11 ms	724 KB	Output is correct
12	Correct	125 ms	988 KB	Output is correct
13	Correct	93 ms	976 KB	Output is correct
14	Correct	93 ms	980 KB	Output is correct
15	Correct	224 ms	1012 KB	Output is correct
16	Correct	188 ms	1048 KB	Output is correct
17	Correct	220 ms	1084 KB	Output is correct
18	Correct	214 ms	1092 KB	Output is correct
19	Correct	239 ms	1084 KB	Output is correct
20	Correct	217 ms	1096 KB	Output is correct
21	Correct	233 ms	1092 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	724 KB	Output is correct
3	Correct	1 ms	568 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	724 KB	Output is correct
12	Correct	1 ms	596 KB	Output is correct
13	Correct	9 ms	724 KB	Output is correct
14	Correct	6 ms	852 KB	Output is correct
15	Correct	6 ms	852 KB	Output is correct
16	Correct	10 ms	1108 KB	Output is correct
17	Correct	9 ms	1076 KB	Output is correct
18	Correct	12 ms	1072 KB	Output is correct
19	Correct	277 ms	1000 KB	Output is correct
20	Correct	223 ms	1000 KB	Output is correct
21	Correct	230 ms	1100 KB	Output is correct
22	Correct	235 ms	1076 KB	Output is correct
23	Correct	84 ms	940 KB	Output is correct
24	Correct	190 ms	1064 KB	Output is correct
25	Correct	130 ms	880 KB	Output is correct
26	Correct	107 ms	916 KB	Output is correct
27	Correct	224 ms	1068 KB	Output is correct
28	Correct	220 ms	1068 KB	Output is correct
29	Correct	11 ms	724 KB	Output is correct
30	Correct	125 ms	988 KB	Output is correct
31	Correct	93 ms	976 KB	Output is correct
32	Correct	93 ms	980 KB	Output is correct
33	Correct	224 ms	1012 KB	Output is correct
34	Correct	188 ms	1048 KB	Output is correct
35	Correct	220 ms	1084 KB	Output is correct
36	Correct	214 ms	1092 KB	Output is correct
37	Correct	239 ms	1084 KB	Output is correct
38	Correct	217 ms	1096 KB	Output is correct
39	Correct	233 ms	1092 KB	Output is correct
40	Correct	355 ms	3116 KB	Output is correct
41	Correct	10 ms	960 KB	Output is correct
42	Correct	225 ms	3244 KB	Output is correct
43	Correct	216 ms	2884 KB	Output is correct
44	Correct	208 ms	2928 KB	Output is correct
45	Correct	291 ms	12276 KB	Output is correct
46	Correct	14 ms	1884 KB	Output is correct
47	Correct	279 ms	12384 KB	Output is correct
48	Correct	287 ms	9660 KB	Output is correct
49	Correct	259 ms	10268 KB	Output is correct

Submission #827081

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0