득이공간

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net #include using namespace std; bool PrimeNumber[1000001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int M, N; cin >> M >> N; for (int i = 2; i

11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include #include #include #include using namespace std; const int& MaxSize = 100001; const int& MaxK = 20; int K; int MaxDepth; list Neighbors[MaxSize]; int Depth[MaxSize]; int Parent[MaxK][MaxSize]; queue SearchQueue; bool Visited[MaxSize]; void SearchLC..

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include #include #include using namespace std; const int& MaxSize = 10001; list Children[MaxSize]; pair Tree[MaxSize]; queue SearchQueue; void SearchLCA(int NodeA, int NodeB) { int A = NodeA; int B = NodeB; while (Tree[A].second !..

11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include #include #include using namespace std; const int& MaxSize = 50001; list Neighbors[MaxSize]; pair Tree[MaxSize]; queue SearchQueue; bool Visited[MaxSize]; void SearchLCA(int NodeA, int NodeB) { int A = NodeA; int B = NodeB; while (Tree[A].second != T..

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include #include using namespace std; const int& DivNum = 1000000007; int Count, StartIndex; long long MulTree[1048576 * 2]; void UpdateValue(int Index, int Value) { int CurIndex = StartIndex + Index; MulTree[CurIndex] = Valu..

10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net #include #include using namespace std; int Count, StartIndex; int MinTree[131072 * 2]; void SearchMinimumValue(int Start, int End) { int CurStart = StartIndex + Start; int CurEnd = StartIndex + End; int MinValue = 1000000001; while (CurStart..

2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net #include #include using namespace std; int Count, StartIndex; int MinTree[131072 * 2]; int MaxTree[131072 * 2]; void SearchTree(int N, int Start, int End) { int CurStart = StartIndex + Start; int CurEnd = StartIndex + End; int Min = 100000..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include #include using namespace std; int Count, StartIndex; long long SegmentTree[1048576 * 2]; void UpdateTree(int N, int Index, long long Value) { int Current = StartIndex + Index; SegmentTree[Current] = Value; for (int i =..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #include #include using namespace std; string PreorderTree; string InorderTree; string PostorderTree; char Tree[27][2]; void DFS(char Parent) { if (Parent == '.') { return; } char LeftChild = Tree[Parent - 65][0]; char RightChild = Tree[Parent - 65][1]; ..

1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net #include #include #include using namespace std; vector OrderedList; void Test() { int N; cin >> N; OrderedList.reserve(N); OrderedList.clear(); pair Ranks; for (int i = 0; i > Ranks.first >> Ranks.second; OrderedList.emplace_back(R..