Guest User

Untitled

a guest
Jun 27th, 2013
460
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <stack>
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <math.h>
  8. #include <queue>
  9. #include <map>
  10. #include <set>
  11. #include <limits.h>
  12. #include <limits>
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <sstream>
  16. #include <string.h>
  17. #include <assert.h>
  18. #include <numeric>
  19. using namespace std;
  20.  
  21. int N, dp[100005];
  22. pair <int, int> country[100005];
  23.  
  24. vector <int> tree[4 * 100005];
  25. void build(int i, int L, int R){
  26.     if(L == R)tree[i].push_back(country[L].second);
  27.     else{
  28.         int mid = (L + R) >> 1;
  29.         build(2 * i, L, mid);
  30.         build(2 * i + 1, mid + 1, R);
  31.        
  32.         merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(),
  33.                 back_inserter(tree[i]));
  34.     }
  35. }
  36. int query(int i, int L, int R, int s, int t, int k){
  37.     if(t < s)return 0;
  38.    
  39.     if(s <= L && R <= t){
  40.         return (lower_bound(tree[i].begin(), tree[i].end(), k) - tree[i].begin());
  41.     }else if(R < s || t < L)return 0;
  42.     else{
  43.         int mid = (L + R) >> 1;
  44.         return query(2 * i, L, mid, s, t, k) + query(2 * i + 1, mid + 1, R, s, t, k);
  45.     }
  46. }
  47. int main(){
  48.     scanf("%d", &N);
  49.     for(int i = 0; i < N; i++)
  50.         scanf("%d %d", &country[i].second, &country[i].first);
  51.     sort(country, country + N);
  52.  
  53.     for(int i = 0; i < (4 * 100005); i++)
  54.         tree[i].clear();
  55.     build(1, 0, N - 1);
  56.  
  57.     dp[N] = 0;
  58.     for(int x = N - 1; x >= 0; x--){
  59.         int y = max(x + 1, lower_bound(country, country + N, make_pair(country[x].second, 0)) - country);
  60.  
  61.         dp[x] = 1 + dp[y] + query(1, 0, N - 1, x + 1, y - 1, country[x].first);
  62.         dp[x] = max(dp[x], dp[x + 1]);
  63.     }
  64.  
  65.     printf("%d\n", dp[0]);
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment