# P2519: problem a [HAOI2011]

Problem Description: N students are in classroom, the ith student says there are $$a_i$$ students that have scores higher than me and $$b_i$$ students that have scores lower than me(There might exist same scores). Please give out the minimum possible number of students that are lying.

Input Format:
First line with one integer N ≤ 100000
Next N lines with two integers denoting $$a_i,b_i$$

Output Format:
One line with the minimum possible number of lying students.

Sample Input:
3 2 0 0 2 2 2

Sample Output:
1

Solution: This is one DP problem. First, we notice that which $$a_i$$ persons do not affect the result. Secondly, we are trying to maximize the number of students that are not lying. For each given $$a_i$$ and $$b_i$$, we transform it into a range l = $$a_i$$ + 1 and r = N – $$b_i$$. If l > r, it is obviously wrong. If r – l + 1 is less than the number of persons who claimed they are in this range, then the part that exceeds r – l + 1 is false. We say for each range [l,r], there is a weight equals to the maximum number of people who can be in this range. We have following DP formula:
$$f[i] = \max(f[i – 1],f[k] + V_i)$$, where f[i] denotes the maximum people that can be in the first i ranges and 1 ≤ k ≤ i – 1. Then the answer equals to N – f[m].

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
#define inf 0x7f7f7f7f
const int maxn = 100005;
int N,f[maxn];
struct node{
int l,r,v;
node(int a = 0,int b = 0,int c = 0):l(a),r(b),v(c){};
} a[maxn],b[maxn];
bool cmp1(node a,node b){
if(a.l != b.l) return a.l < b.l;
return a.r < b.r;
}
bool cmp2(node a,node b){
if(a.r != b.r) return a.r < b.r;
return a.l < b.l;
}
int bin_search(int l,int r,int x){
while(l <= r){
int mid = (l + r) >> 1;
if(a[mid].r < x) l = mid + 1;
else r = mid - 1;
}
return r;
}
int main(){
FAST_IO
cin>>N;
for(int i = 1; i <= N; i++){
cin>>a[i].l>>a[i].r;
a[i].l++;
a[i].r = N - a[i].r;
}
sort(a + 1, a + 1 + N,cmp1);
int cnt1 = 0,cnt2 = 0;
for(int i = 1; i <= N; i++) if(a[i].l <= a[i].r) b[++cnt1] = a[i];
for(int i = 1; i <= cnt1; i++){
if(b[i].l != b[i - 1].l || b[i].r != b[i - 1].r){
a[++cnt2] = b[i];
a[cnt2].v = 1;
}
else{
a[cnt2].v++;
a[cnt2].v = min(a[cnt2].v,a[cnt2].r - a[cnt2].l + 1);
}
}
sort(a + 1,a + 1 + cnt2,cmp2);
f[1] = a[1].v;
for(int i = 2; i <= cnt2; i++){
int k = bin_search(1,i-1,a[i].l);
f[i] = max(f[i - 1],f[k] + a[i].v);
}
cout<<N - f[cnt2]<<endl;
return 0;
}