oj.uz

Submission #95183

# Submission time Handle Problem Language Result Execution time Memory
95183 2019-01-28T09:29:12 Z Retro3014 Lottery (CEOI18_lot) C++17
0 / 100
 610 ms 888 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

#define MAX_N 100000
#define MAX_Q 100

using namespace std;

int N, L, Q;
int ans[MAX_Q+1][MAX_N+1];
int calc2[MAX_Q+1][MAX_N+1];
vector<int> v;

struct Query{
	Query (int idx, int data) : idx(idx), data(data) {}
	int idx, data;
	bool operator <(const Query &a)const{
		return data<a.data;
	}
};
vector<Query> query;
vector<int> q;

void calc(int x, int y){
	y = lower_bound(q.begin(), q.end(), y)-q.begin();
	calc2[y][x]++;
}

int main(){
	scanf("%d %d", &N, &L);
	int x;
	for(int i=0; i<N; i++){
		scanf("%d", &x); v.push_back(x);
	}
	scanf("%d", &Q);
	for(int i=0; i<Q; i++){
		scanf("%d", &x);	query.push_back({i, x});
		q.push_back(x);
	}
	sort(q.begin(), q.end()); sort(query.begin(), query.end());
	for(int i=1; i+L-1<N; i++){
		int s1 = 0, s2 = i, e1 = -1, e2 = i-1;
		int cnt=0;
		while(e2<N){
			if(e1-s1+1 == L){
				calc(s1, cnt); calc(s2, cnt);
				//printf("%d %d %d\n", s1, s2, cnt);
				cnt-=(v[s1]!=v[s2]); s1++; s2++;
			}else{
				e1++; e2++;
				if(e2==v.size())	break;
				cnt+=(v[e1]!=v[e2]);
			}
		}
	}
	for(int i=0; i<Q; i++){
		for(int j=0; j<N; j++){
			calc2[i][j] += calc2[i-1][j];
			ans[query[i].idx][j] = calc2[i][j];
		}
	}
	for(int i=0; i<Q; i++){
		for(int j=0; j<N-L+1; j++){
			printf("%d ", ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:53:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(e2==v.size()) break;
        ~~^~~~~~~~~~
lot.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x); v.push_back(x);
   ~~~~~^~~~~~~~~~
lot.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
lot.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x); query.push_back({i, x});
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 610 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 610 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -