code chef - Divide the Tangerine 橘子分塊算法題解

Once Chef decided to divide the tangerine into several parts. At first, he numbered tangerine's segments from1 to n in the clockwise order starting from some segment. Then he intended to divide the fruit into several parts. In order to do it he planned to separate the neighbouring segments in k places, so that he could get kparts: the 1^st - from segment l₁ to segment r₁ (inclusive), the 2^nd - from l₂ to r₂, ..., the k^th - from l_k to r_k (in all cases in the clockwise order). Suddenly, when Chef was absent, one naughty boy came and divided the tangerine into p parts (also by separating the neighbouring segments one from another): the 1^st - from segment a₁ to segment b₁, the 2^nd - from a₂ to b₂, ..., the p^th - from a_p to b_p (in all cases in the clockwise order). Chef became very angry about it! But maybe little boy haven't done anything wrong, maybe everything is OK? Please, help Chef to determine whether he is able to obtain the parts he wanted to have (in order to do it he can divide p current parts, but, of course, he can't join several parts into one).

Please, note that parts are not cyclic. That means that even if the tangerine division consists of only one part, but that part include more than one segment, there are two segments which were neighbouring in the initial tangerine but are not neighbouring in the division. See the explanation of example case 2 to ensure you understood that clarification.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three space separated integers n, k, p, denoting the number of tangerine's segments and number of parts in each of the two divisions. The next k lines contain pairs of space-separated integers l_i and r_i. The next p lines contain pairs of space-separated integers a_i and b_i.

It is guaranteed that each tangerine's segment is contained in exactly one of the first k parts and in exactly one of the next p parts.

Output

For each test case, output a single line containing either "Yes" or "No" (without the quotes), denoting whether Chef is able to obtain the parts he wanted to have.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ n ≤ 5 * 10⁷
• 1 ≤ k ≤ min(500, n)
• 1 ≤ p ≤ min(500, n)
• 1 ≤ l_i, r_i, a_i, b_i ≤ n

  Example

  Input:
  2
  10 3 2
  1 4
  5 5
  6 10
  1 5
  6 10
  10 3 1
  2 5
  10 1
  6 9
  1 10
  
  Output:
  Yes
  No
  

  Explanation

  Example case 1: To achieve his goal Chef should divide the first part (1-5) in two by separating segments 4 and 5 one from another.

  Example case 2: The boy didn't left the tangerine as it was (though you may thought that way), he separated segments 1 and 10 one from another. But segments 1 and 10 are in one part in Chef's division, so he is unable to achieve his goal.

  
  

  好長的題目，本題目的難度就是如何讀懂題目了。

  題目解析：

  1 把一個橘子分塊，然後分堆，所有堆中有的快的序號必須是順時針數起

  2 分堆已經亂了

  3 是否在亂了的堆中分出原來想要分的堆？

  額外隱藏條件： 1 所有堆都需要分出來 2 不能合並堆，只能分開堆

  讀懂題目就能出答案了，尤其是隱藏條件

  注意：

  1 輸出格式Yes不是YES

  2 vector容器每次都需要清零

  這個程序的時間效率有點復雜，是：O(lg(k)*max(k, p))

  #include 
  #include 
  #include 
  #include 
  
  using namespace std;
  
  struct Tangerine
  {
  	int left, right;
  	bool operator<(const Tangerine &t) const
  	{
  		return left < t.left;
  	}
  };
  
  bool biDiv(vector &vk, int low, int up, int left)
  {
  	if (low > up) return false;
  	int mid = low + ((up-low)>>1);
  	if (vk[mid].left < left) return biDiv(vk, mid+1, up, left);
  	if (left < vk[mid].left) return biDiv(vk, low, mid-1, left);
  	return true;
  }
  
  string divTangerine(vector &vk, vector &vp)
  {
  	sort(vk.begin(), vk.end());
  	for (unsigned i = 0; i < vp.size(); i++)
  	{
  		if (!biDiv(vk, 0, vk.size()-1, vp[i].left)) return "No";
  	}
  	return "Yes";
  }
  
  void DivideTheTangerine()
  {
  	int n = 0, k = 0, p = 0;
  	Tangerine tang;
  	vector vk;
  	vector vp;
  
  	int T = 0;
  	cin>>T;
  	while (T--)
  	{
  		cin>>n>>k>>p;
  		for (int i = 0; i < k; i++)
  		{
  			cin>>tang.left>>tang.right;
  			vk.push_back(tang);
  		}
  		for (int i = 0; i < p; i++)
  		{
  			cin>>tang.left>>tang.right;
  			vp.push_back(tang);
  		}
  		
  		cout<
  
  OJ: http://www.codechef.com/problems/TANGDIV