Submission #883807

#	Time	Username	Problem	Language	Result	Execution time	Memory
883807		phoenix0423	Lottery (CEOI18_lot)	C++17	100 / 100	389 ms	12704 KiB

lot

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define int long long 
const ll INF = 1e18;
const int maxn = 1e4 + 5;
const int A = 937521937;
const int B = 998244353;
int n, l;
int a[maxn];
int nxt[maxn];
vector<int> val;

signed main(void){
	fastio;
	cin>>n>>l;
	for(int i = 0; i < n; i++) cin>>a[i];
	int q;
	cin>>q;
	vector<int> qry(q);
	for(int i = 0; i < q; i++){
		cin>>qry[i];
		val.pb(qry[i]);
	}
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
	int cur = 0;
	for(int i = 0; i <= n; i++){
		nxt[i] = cur;
		if(i == val[cur]) cur++;
		if(cur == val.size()){
			i++;
			while(i <= n) nxt[i] = INF, i++;
		}
	}
	vector<vector<int>> d(n, vector<int>(val.size()));
	for(int dist = 1; dist < n; dist++){
		int cur = 0;
		for(int i = 0; i + dist + l - 1 < n; i++){
			if(i == 0){
				for(int k = 0; k < l; k++) if(a[i + k] != a[i + dist + k]) cur++;
			}
			else{
				cur = cur - (a[i - 1] != a[i + dist - 1]) + (a[i + l - 1] != a[i + dist + l - 1]);
			}
			if(nxt[cur] == INF) continue;
			d[i][nxt[cur]] ++, d[i + dist][nxt[cur]] ++;
		}
	}
	for(int i = 0; i < n - l + 1; i++) for(int j = 1; j < val.size(); j++) d[i][j] += d[i][j - 1];
	for(int i = 0; i < q; i++){
		for(int j = 0; j < n - l + 1; j++) cout<<d[j][nxt[qry[i]]]<<" ";
		cout<<"\n";
	}
	

}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:37:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   if(cur == val.size()){
      |      ~~~~^~~~~~~~~~~~~
lot.cpp:56:54: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0; i < n - l + 1; i++) for(int j = 1; j < val.size(); j++) d[i][j] += d[i][j - 1];
      |                                                    ~~^~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20