템플릿
-
VSCode에서 <bits/stdc++.h> precompile header 사용템플릿 2024. 9. 28. 23:04
새로 세팅할때 참고하기 위해 백업 Code Runner 익스텐션의 setting.json에서 -include bits/stdc++ 을 포함"cpp": "cd $dir && g++ -include bits/stdc++ -std=c++20 \"$fileName\" -o \"$fileNameWithoutExt\" && & \"$dir$fileNameWithoutExt\"",stdc++.h와 동일한 위치에서 미리 컴파일:g++ -std=c++20 -x c++-header bits/stdc++.h -o stdc++.gch 적용 여부는 -H에서 봐도 되고, -ftime-report 후 phase parsing 부분을 체크Competitive Programming Helper 에도 -include bits/stdc..
-
lazy 세그템플릿 2022. 5. 2. 01:10
https://www.acmicpc.net/problem/10999 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; ll n, m, k; vector a, segTree, lazy; void updateLazy(ll i, ll s, ll e) { if (lazy[i] != 0) { segTree[i] += (e - s + 1) * lazy[i]; if (s != e) { lazy[i * 2] += lazy[i]; lazy[i * 2 + 1] += lazy[i]; } lazy[i] = 0; } } l..
-
유니온파인드템플릿 2022. 2. 28. 19:02
base : https://www.acmicpc.net/problem/1717 처음에 memset(-1)을 해두고, p[i]의 절대값이 집합의 원소의 개수가 되도록 구현했다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; class UF { public: vector p; UF(int n) { p = vector(n + 1, -1); } int find(int cur) { if (p[cur] n >> m; int i; auto uf = UF(n); for (i = 0..
-
LIS + 역추적템플릿 2022. 2. 4. 15:38
"[14003] 가장 긴 증가하는 부분 수열 5"를 베이스로 둔다. dp로 O(N^2)에 풀 수 있는 문제이지만, 이분탐색으로 O(NlogN)에 동작하도록 만들 수 있고 다익스트라와 마찬가지로 '이전에 어디에서 왔는지'를 저장하면 최장 길이와 해당 수열도 구할 수 있다. 이분탐색은 lower_bound()로 간단하게 구현할 수 있고, iterator를 index처럼 사용하려면 begin()을 빼면 된다. #include using namespace std; using ll = long long; vector a; ll n; void lis(vector& ret) { vector v, path(n); for (ll i = 0; i = 0 && S > 0; i--) { if (path[i] == S - 1)..
-
세그트리템플릿 2021. 11. 14. 09:37
https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net ll update #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; ll n, m, k; vector ..