문제 링크 http://icpc.me/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net 풀이 세그먼트 트리로 dp최적화를 하는 문제다. dp[i] = max(dp[i], max(dp[i - k]) + arr[i]) (1 1) using namespace std; using ll = long long; const int N = 1e5 + 5; ll dp[N]; ll tree[4 * N]; ll query(int node, int s, int e, int qs, in..

문제 링크 http://icpc.me/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀이하였다. 하지만 누적합을 이용하여 더 쉽게 풀이할 수 있는 것 같다. 수열과 쿼리21과 문제가 비슷하여 똑같이 풀이하였다. 자세한 풀이는 저 링크를 참고하자. 코드 #include int seg[400005], arr[100005]; void init(int node, int s, int e) { if (s == e) { seg[node] = arr[s]; return..

문제 링크 http://icpc.me/5419 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net 풀이 스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다. y좌표를 좌표압축을 한 후에 x좌표 기준 오름차순 정렬하고 만약 x좌표가 같다면 y좌표가 큰 순으로 정렬한다. k번째 점과 쌍이 될 수 있는 점의 수는 x좌표가 k보다 작고, y좌표는 k보다 크거나 같은 점의 수이다. 이때 이 점들을 전탐색하면 O(N^2)으로 시간이 터져버린다. 그렇기 때문에 k번째 점과 쌍이 될 수 있는 점의 수를 세그먼트 트리를 이용하여 시간을 줄여줘야 한다. k의 y좌표 ~ 범위 끝까지의 수를 가져오면 빠르게 수를 구할 수 있다. 세그먼트 트리를 ..

문제 링크 http://icpc.me/1517 풀이 세그먼트 트리를 이용하여 풀이 할 수 있다. i > j이면서 arr[i] j를 만족하는 것의 개수만 카운트 하면 된다. 코드 #include #include using namespace std; using ll = long long; pair arr[500005]; ll tree[2000006], ans; ll query(int cur, int s, int e, int qs, int qe) { if (e < qs || qe < s) return 0; if (qs 1; ll left..