oj.uz

Submission #827033

# Submission time Handle Problem Language Result Execution time Memory
827033 2023-08-16T08:15:14 Z sentheta Lottery (CEOI18_lot) C++17
35 / 100
 308 ms 1100 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[N];
V<int> qans[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){
		qans[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];
		}
		qans[find(diff)][i]++;
		qans[find(diff)][j]++;
		
		// continue compare
		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];

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 1004 KB Output is correct
2 Correct 240 ms 1000 KB Output is correct
3 Correct 222 ms 1008 KB Output is correct
4 Correct 214 ms 1100 KB Output is correct
5 Correct 71 ms 944 KB Output is correct
6 Correct 245 ms 1064 KB Output is correct
7 Correct 72 ms 852 KB Output is correct
8 Correct 109 ms 912 KB Output is correct
9 Correct 204 ms 1068 KB Output is correct
10 Correct 212 ms 1072 KB Output is correct
11 Correct 13 ms 820 KB Output is correct
12 Correct 115 ms 992 KB Output is correct
13 Correct 94 ms 964 KB Output is correct
14 Correct 128 ms 980 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 1004 KB Output is correct
2 Correct 240 ms 1000 KB Output is correct
3 Correct 222 ms 1008 KB Output is correct
4 Correct 214 ms 1100 KB Output is correct
5 Correct 71 ms 944 KB Output is correct
6 Correct 245 ms 1064 KB Output is correct
7 Correct 72 ms 852 KB Output is correct
8 Correct 109 ms 912 KB Output is correct
9 Correct 204 ms 1068 KB Output is correct
10 Correct 212 ms 1072 KB Output is correct
11 Correct 13 ms 820 KB Output is correct
12 Correct 115 ms 992 KB Output is correct
13 Correct 94 ms 964 KB Output is correct
14 Correct 128 ms 980 KB Output is correct
15 Correct 231 ms 1000 KB Output is correct
16 Correct 187 ms 1052 KB Output is correct
17 Correct 245 ms 1076 KB Output is correct
18 Correct 241 ms 1076 KB Output is correct
19 Correct 276 ms 1072 KB Output is correct
20 Correct 215 ms 1084 KB Output is correct
21 Correct 241 ms 1084 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -