Subscribed unsubscribe Subscribe Subscribe

0w1

CF 527C Glass Carving ( STL set )

Problem - C - Codeforces The key is to realize that the largest area is the largest width * largest height. They can be maintained with STL set / multiset separately. For each of them, prepare a set to keep record of the existing lines. Wh…

UVA 12538 Version Controlled IDE ( 持久化隨機二元搜尋樹 )

UVa Online Judge - Offline Here are some good resources I read through in order to understand how to implement persistent RBST for this problem. morris821028.github.io blog.csdn.net #include <bits/stdc++.h> using namespace std; const int MAXMEM = 5e7; co</bits/stdc++.h>…

Persistent segment tree

2104 -- K-th Number Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar. First we discretize the integers so that there are at most 1e5 inte…

Lowest common ancestor

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…

Randomized binary search tree

いつか貼ろうと思ってました。始めて学べた頃は可読性の高いソースコード見当たらなくて(中国人のコードはもう。。)、理解に色々と苦労しましたOrz、もちろん自分のがわかりやすいとも言えませんが、もし分からない部分があれば是非コメントして下さい、知…

Introduction to deque optimizations

A deque ( double ended queue ) is a data structure that supports push/ pop from both ends with constant time complexity. It can be used to optimize algorithms that deal with monotonous properties. The first time I saw this data structure, …

Introduction to stack optimizations

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem. Here are some problems for exercise from the ant book. 3250 -- Bad Hair Day POJ 3250 Bad Ha…

Randomized binary search tree on value

I have never wrote one to split by value, but for segments. Here's a simple problem that gave me my first chance to solve one like that. http://zerojudge.tw/ShowProblem?problemid=d794 World Ranking The input will give you scores, and you h…