https://www.acmicpc.net/problem/7469 Persistent Segment Tree와 비슷한 Persistent Indexed Tree(?)를 구현해서 통과했다. 실제로 구현해 본 건 처음이었는데 예전에 명우씨한테 잠깐 설명들었던게 도움이 됐다. (Persistent Segment Tree에 대한 설명은 요기에) vector로 내맘대로 구현했는데, lower_bound썼으면 좀 더 깔끔했을듯.. 시간복잡도는 O(Mlog²N) 자세한 설명은 다음에... 테스트케이스 : (출처 : NEERC Subregional Contest) #include #include #include #include #define MAXN 262150#define INF 1987654321using name..

Red-Black Tree특징모든 node는 BLACK 또는 RED의 색을 가진다.root node는 항상 BLACK이다.leaf node도 항상 BLACK이다.RED가 연속되어 있을 수 없다. (부모-자식간)root node부터 leaf node사이의 BLACK의 개수는 동일하다.self-balancing BST로 일반 BST와 다르게 5번 규칙에 의해 skewed binary tree가 되지 않음이 보장된다. (삽입/삭제 O(lgN) 보장)동작색상을 RED = 0, BLACK = 1, DOUBLE-BLACK = 2로 생각하면 이해하기 편하다.조회BST와 동일하게 수행삽입새로 삽입되는 노드는 항상 RED로 시작한다.부모노드가 조부노드의 왼쪽 자식인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)부..

http://codeforces.com/problemset/problem/913/D D. Too Easy Problemstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are preparing for an exam on scheduling theory. The exam will last for exactly T milliseconds and will consist of n problems. You can either solve problem i in exactly ti milliseconds or ignore it and spend no time. You don't..

http://codeforces.com/problemset/problem/909/D D. Colorful Pointstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a set of points on a straight line. Each point has a color assigned to it. For point a, its neighbors are the points which don't have any other points between them and a. Each point has at most two neighbors - one fro..

http://codeforces.com/problemset/problem/909/C C. Python Indentationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.We will consider an extremely simplified subset of Python with only two..

http://codeforces.com/problemset/problem/900/CC. Remove Extra Onetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output You are given a permutation p of length n. Remove one element from permutation to make the number of records the maximum possible.We remind that in a sequence of numbers a1, a2, ..., ak the element ai is a record if for every inte..

http://codeforces.com/contest/832/problem/D D. Misha, Grisha and Underground time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputMisha and Grisha are funny boys, so they like to use new underground. The underground has n stations connected with n - 1 routes so that each route connects two stations, and it is possible to reach every station from a..

http://codeforces.com/contest/831/problem/E E. Cards Sortingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputVasily has a deck of cards consisting of n cards. There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive. It is possible that some cards have the same integers on them.Vasily decided to sort the cards...

http://codeforces.com/problemset/problem/831/C C. Jury Markstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp watched TV-show where k jury members one by one rated a participant by adding him a certain number of points (may be negative, i. e. points were subtracted). Initially the participant had some score, and each the marks were one..

https://www.acmicpc.net/problem/1626 두 번째로 작은 스패닝 트리 방향성이 없는 그래프 G가 있고 이 그래프에서의 최소 스패닝 트리 T가 존재한다. 문제는 최소 스패닝 트리 T보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다.MST와 second MST의 모습입력첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다.출력두 번째로 작은 스패닝 트리의 값을 출력한다. 만약 스패닝 트리나 두 번재로 작은 스패..