Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <stack>
- #include <algorithm>
- #include <bitset>
- #include <math.h>
- #include <queue>
- #include <map>
- #include <set>
- #include <limits.h>
- #include <limits>
- #include <stdio.h>
- #include <stdlib.h>
- #include <sstream>
- #include <string.h>
- #include <assert.h>
- #include <numeric>
- using namespace std;
- int N, dp[100005];
- pair <int, int> country[100005];
- vector <int> tree[4 * 100005];
- void build(int i, int L, int R){
- if(L == R)tree[i].push_back(country[L].second);
- else{
- int mid = (L + R) >> 1;
- build(2 * i, L, mid);
- build(2 * i + 1, mid + 1, R);
- merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(),
- back_inserter(tree[i]));
- }
- }
- int query(int i, int L, int R, int s, int t, int k){
- if(t < s)return 0;
- if(s <= L && R <= t){
- return (lower_bound(tree[i].begin(), tree[i].end(), k) - tree[i].begin());
- }else if(R < s || t < L)return 0;
- else{
- int mid = (L + R) >> 1;
- return query(2 * i, L, mid, s, t, k) + query(2 * i + 1, mid + 1, R, s, t, k);
- }
- }
- int main(){
- scanf("%d", &N);
- for(int i = 0; i < N; i++)
- scanf("%d %d", &country[i].second, &country[i].first);
- sort(country, country + N);
- for(int i = 0; i < (4 * 100005); i++)
- tree[i].clear();
- build(1, 0, N - 1);
- dp[N] = 0;
- for(int x = N - 1; x >= 0; x--){
- int y = max(x + 1, lower_bound(country, country + N, make_pair(country[x].second, 0)) - country);
- dp[x] = 1 + dp[y] + query(1, 0, N - 1, x + 1, y - 1, country[x].first);
- dp[x] = max(dp[x], dp[x + 1]);
- }
- printf("%d\n", dp[0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment