1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define maxn 1000005 5 #define lowbit(x) (-x&x) 6 using namespace std; 7  8 int n,high = 0; 9 10 struct node{11     int pos,ai;12 }list[maxn];13 14 int Tree[maxn],DP[maxn],minn;15 int sum(int p){16     int ans = 0;17     while(p){18 //        cout << ‘^‘;19 //        cout << p;20         ans += Tree[p];21         p -= lowbit(p);22     }23     return ans;24 }25 void add(int p){26     while(p <= high){27 //        cout << ‘G‘;28         Tree[p]++;29         p += lowbit(p);30 //        cout << p;31     }32 }33 34 bool cmp(const node &a,const node &b){35     return a.pos < b.pos;36 }37 38 int main(){39     scanf("%d",&n);40     41     for(int i = 1;i <= n;i++){42         scanf("%d%d",&list[i].pos,&list[i].ai);43         list[i].pos++;44         high = max(high,list[i].pos);45     }46     47     sort(list+1,list+1+n,cmp);48     49 //    printf("#%d#\n",high);50     51     for(int i = 1;i <= n;i++){52         53 //        cout << ‘A‘;54         add(list[i].pos);55     }56     57     for(int i = 1;i <= n;i++){58         int a = list[i].pos-1;59         int b = list[i].pos-list[i].ai-1;60         if(a < 0) a = 0;61         if(b < 0) b = 0;62         int y = sum(a)-sum(b);63         if(i-y-1 < 0) continue;64         DP[i] = DP[i-y-1] + y;65     }66     67     minn = DP[n];68     69     for(int i = 1;i <= n;i++){70         minn = min(minn,DP[i]+n-i);71     }72     73     printf("%d",minn);74     75 //    cout << endl;76 //    for(int i = 0;i <= n;i++) printf("%d ",DP[i]);77     78 //    cout << endl;79 //    for(int i = 0;i <= 10;i++) printf("%d ",sum(i));80     81     return 0;82 }