글 읽기 - 틀리는 부분이 있을까요???

kioio5 6년 전 0

정렬한 후에 세그먼트 트리로 구현했습니다..

어디가 잘못되었을까요..ㅠㅠㅠㅠㅠ......

#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;

#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
//ios::sync_with_stdio(false); cin.tie(0);

typedef struct {
	int d; // 실력
	int list; // 알고리즘 리스트bit
}info;

info s[MAX_SIZE];
pair<int, int> tree[1 << 18];
int n, k, d;

bool cmp(info a, info b) {
	return a.d < b.d;
}

int max(int a, int b) {
	return a > b ? a : b;
}

//알고리즘 수, 알고리즘 리스트
pair<int, int> init(int node, int start, int end) {
	if (start == end) return tree[node] = mp(s[start].list, s[start].list);

	int mid = (start + end) / 2;
	pair<int, int> left = init(node * 2, start, mid);
	pair<int, int> right = init(node * 2 + 1, mid + 1, end);

	return tree[node] = mp(left.first | right.first, left.second & right.second);
}

pair<int, int> query(int node, int start, int end, const int left, const int right) {
	//이부분이 잘못되었네요!!!
    //if (right < start || end < left) return mp(0, (1 << n) - 1);
    //아래로 바꿔서 맞았습니다!!
    //알고리즘 수만큼 해줘야하는데..모르고 n만큼 쉬프트해버렸넹..ㅠㅠ
    if (right < start || end < left) return mp(0, (1 << k) - 1);
	else if (left <= start && end <= right) return tree[node];
	else {
		int mid = (start + end) / 2;
		pair<int, int> leftChild = query(node * 2, start, mid, left, right);
		pair<int, int> rightChild = query(node * 2 + 1, mid + 1, end, left, right);

		return mp(leftChild.first | rightChild.first, leftChild.second & rightChild.second);
	}
}

int count(int n) {
	int ret = 0;
	while (n) {
		ret += n % 2;
		n /= 2;
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> k >> d;

	for (int i = 0; i < n; i++) {
		int cnt;
		cin >> cnt >> s[i].d;

		for (int j = 0; j < cnt; j++) {
			int a;
			cin >> a;

			s[i].list |= 1 << (a - 1);
		}
	}

	sort(s, s + n, cmp);

	init(1, 0, n - 1);

	int ret = 0;
	int left = 0, right = 0;

	while (right < n) {
		if (s[right].d - s[left].d <= d) {
			pair<int, int> tmp = query(1, 0, n - 1, left, right);
			ret = max(ret, (count(tmp.first) - count(tmp.second)) * (right - left + 1));
			right++;
		}
		else left++;
	}
	cout << ret;

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀리는 부분이 있을까요???

kioio5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말