[백준 20438] 출석체크

문제

www.acmicpc.net/problem/20438

20438번: 출석체크

 

풀이

1. 조는 친구들을 우선 체크한 후, 출석 번호를 받은 친구들의 배수마다 출석했다고 체크를 하는데 조는 친구들은 무시하고 넘어가면 됩니다.

 

2. 이 때 구간질의마다 학생 수를 세면 시간초과가 나기 때문에 미리 누적합 배열을 저장해놓고, [s, e] 구간의 합에 대해psum[e] - psum[s - 1]을 출력하면 해결할 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, k, q, m, x, s, e, add;
bool sleep[5005], chk[5005];
vector<int> psum;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k >> q >> m;
	psum.resize(n + 3, 0);
	while (k--) {
		cin >> x;
		sleep[x] = 1;
	}
	while (q--) {
		cin >> x;
		if (sleep[x]) continue;
		add = x;
		while (x <= n + 2) {
			if (sleep[x]) {
				x += add;
				continue;
			}
			chk[x] = 1, x += add;
		}
	}
	for (int i = 3; i <= n + 2; i++) psum[i] = psum[i - 1] + (chk[i] == 0);
	for (int i = 0; i < m; i++) {
		cin >> s >> e;
		cout << psum[e] - psum[s - 1] << '\n';
	}
}