P2519-[HAOI2011]problem a

 1 #include <bits/stdc++.h>
 2 #define _for(i,a,b) for(register int i = (a);i < b;i ++)
 3 #define _rep(i,b) for(register int i = (a);i > b;i --)
 4 #define INF 0x3f3f3f3f
 5 #define MOD 100000000
 6 #define maxn 150003
 7 #define pb push_back
 8 typedef long long ll;
 9 
10 using namespace std;
11 typedef pair<int,int> P;
12 inline ll read()
13 {
14     ll ans = 0;
15     char ch = getchar(),last = ‘ ‘;
16     while(!isdigit(ch)) last = ch,ch = getchar();
17     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘,ch = getchar();
18     if(last == ‘-‘) ans = -ans;
19     return ans;
20 }
21 inline void write(ll x)
22 {
23     if(x < 0) x = -x,putchar(‘-‘);
24     if(x >= 10) write(x / 10);
25     putchar(x % 10 + ‘0‘);
26 }
27 struct line
28 {
29     int l;
30     int r;
31     int w;
32     bool operator < (line b)
33     {
34         if(r != b.r)
35             return r < b.r;
36         return l < b.l;
37     }
38 };
39 int N;
40 vector<line> v;
41 map<pair<int,int>,int> m;
42 int dp[maxn];
43 int binarysearch(int l,int r,int val)
44 {
45     while(l <= r)
46     {
47         int mid = (l + r) / 2;
48         if (v[mid].r < val) 
49             l = mid + 1;
50         else 
51             r = mid - 1;
52     }
53     return r;
54 }
55 int main()
56 {
57     N = read();
58     _for(i,1,N+1)
59     {
60         int a = read();
61         int b = read();
62         if(a+b+1>N) continue;
63         m[{a+1,N-b}] ++;
64     }
65     v.pb({});
66     for(auto p:m)
67     {
68         line tmp;
69         int d = p.first.second-p.first.first+1;
70         tmp.l = p.first.first;
71         tmp.r = p.first.second;
72         tmp.w = min(d,p.second);
73         v.pb(tmp);
74     }
75 
76     sort(v.begin(),v.end());
77 
78     dp[1] = v[1].w;
79     _for(i,2,v.size())
80     {
81         int nxt = binarysearch(1,i-1,v[i].l);
82         dp[i] = max(dp[i-1],dp[nxt] + v[i].w);
83     }
84     write(N-dp[v.size()-1]);
85     return 0;
86 }