oj.uz

Submission #1022503

# Submission time Handle Problem Language Result Execution time Memory
1022503 2024-07-13T15:35:49 Z vjudge1 Lottery (CEOI18_lot) C++17
45 / 100
 97 ms 924 KB 
// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e4 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,l,q,a[MAX];
int qrx[MAX];
bool idx[MAX];
int nxt[MAX];
int ans[105][MAX];

signed main(){
	
	read();
	
	cin >> n >> l;
	
	for(int i = 1;i <= n;i++)cin >> a[i];
	
	cin >> q;
	
	vector<int> rt;
	
	for(int i = 1;i <= q;i++){
		cin >> qrx[i];		
		idx[qrx[i]] = 1;
		rt.push_back(qrx[i]);
	}
	
	sort(rt.begin(),rt.end());
	rt.erase(unique(rt.begin(),rt.end()),rt.end());
	
	int k = rt.size() + 1;
	
	for(int i = n;i >= 0;i--){
		if(idx[i])k--;
		nxt[i] = k;
	}
	
	
	vector<int> f(n + 5,0);
	for(int len = 1;len <= n;len++){
		for(int i = 1;i <= n;i++)
			f[i] = f[i - 1] + (a[i] != a[i + len]);
		for(int i = 1;i + l - 1 <= n;i++){
			if(i + len + l - 1 > n)break;
			int cost = nxt[f[i + l - 1] - f[i - 1]];
			ans[cost][i]++;
			ans[cost][i + len]++;
		}
	}
	
	for(int i = 1;i <= (int)rt.size();i++){
		for(int j = 1;j <= n;j++){
			ans[i][j] += ans[i - 1][j];
		}
	}
	
	for(int i = 1;i <= q;i++){
		int x = lower_bound(rt.begin(),rt.end(),qrx[i]) - rt.begin() + 1;
		for(int j = 1;j <= n - l + 1;j++)cout << ans[x][j] << " \n"[j == n - l + 1];
	}
	
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 7 ms 576 KB Output is correct
14 Correct 6 ms 600 KB Output is correct
15 Correct 5 ms 664 KB Output is correct
16 Correct 9 ms 860 KB Output is correct
17 Correct 7 ms 652 KB Output is correct
18 Correct 7 ms 604 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 7 ms 576 KB Output is correct
14 Correct 6 ms 600 KB Output is correct
15 Correct 5 ms 664 KB Output is correct
16 Correct 9 ms 860 KB Output is correct
17 Correct 7 ms 652 KB Output is correct
18 Correct 7 ms 604 KB Output is correct
19 Runtime error 97 ms 924 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -