GPD2021

https://www.acmicpc.net/problem/15806 15806번: 영우의 기숙사 청소 통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검 www.acmicpc.net // https://www.acmicpc.net/problem/15806 // 영우의 기숙사 청소 // 큐 class Item { public next: Item | null = null; constructor(public value: any) {} } class Queue { public head: Item | null = null; public tail: Item | null = null..

https://www.acmicpc.net/problem/1385 1385번: 벌집 첫째 줄에는 당신이 있는 방의 번호 a와 출구가 있는 방의 번호 b가 주어진다.1 ≤ a, b ≤ 1,000,000) www.acmicpc.net //https://www.acmicpc.net/problem/1385 // 벌집 const [S, E]: number[] = require('fs').readFileSync('./dev/stdin').toString().trim().split(' ').map(Number); const honeycomb = Array.from(new Array(1000002), () => new Array(6).fill(0)); honeycomb[1] = [2, 0, 0, 0, 0, 0]; ho..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net //https://www.acmicpc.net/problem/6588 // 골드바흐의 추측 const input: number[] = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n').map(Number); input.pop(); const isPrime = new Array(1000001).fi..

https://www.acmicpc.net/problem/14245 14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net //https://www.acmicpc.net/problem/14245 // XOR // 느리게 갱신되는 세그먼트트리 재귀 구현 class LazySegmentTree { constructor(inputArray) { this.n = inputArray.length; this.lg = Math.ceil(Math.log2(this.n)); this.sz = 1

https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net //https://www.acmicpc.net/problem/1395 // 스위치 // 구간 업데이트는 lazy하게 class Node { constructor(on = 0, off = 1) { this.on = on; this.off = off; } } // 느리게 갱신되는 세그먼트 트리 재귀 구현 class LazySegmentTree { construc..

https://www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 비재귀 구현 시간초과 나서 재귀 구현 //https://www.acmicpc.net/problem/12844 // XOR // 구간 업데이트는 lazy하게 // 느리게 갱신되는 세그먼트 트리 재귀 구현 class LazySegmentTree { constructor(inputArray) { this.n = inputArray.length; thi..

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net //https://www.acmicpc.net/problem/16975 // 수열과 쿼리 21 // 구간 합 // 느리게 갱신되는 세그먼트 트리의 비재귀 구현 class Node { constructor(value = 0, size = 0) { this.value = value; this.size = size; } } class NonRecursiveSegmentTreeWith..

https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인 www.acmicpc.net //https://www.acmicpc.net/problem/14428 // 수열과 쿼리 16 // 최솟값의 인덱스 class Node { constructor(value = Infinity, index = Infinity) { this.value = value; this.index = index; } } clas..