CS Academy Dominant Free Sets

题目链接：https://csacademy.com/contest/archive/task/dominant-free-sets/statement/

题目大意：给一个包含N个点的集合，集合中的点各不相同。对于点A,B，如果B.X >= A.X 并且 B.Y >= A.Y，那么认为B优于A。问不存在两个点A,B使得A优于B的集合共多少个。结果对1e9+7取余。10^5

 1 const int maxn = 1e5 + 10;
 2 typedef long long ll;
 3 const ll mod = 1e9 + 7;
 4 int n;
 5 int px[maxn], py[maxn], f[maxn];
 6 ll bit[maxn];
 7 
 8 int lowbit(int x){
 9     return x & (-x);
10 }
11 void add(int x, ll v){
12     while(x <= 1e5){
13         bit[x] = bit[x] % mod + v % mod;
14         bit[x] %= mod;
15         x += lowbit(x);
16     }
17 }
18 ll sum(int x){
19     ll ans = 0;
20     while(x > 0){
21         ans = ans % mod + bit[x] % mod;
22         ans %= mod;
23         x -= lowbit(x);
24     }
25     return ans % mod;
26 }
27 bool cmp(int i, int j){
28     if(px[i] != px[j]) return px[i] < px[j];
29     return py[i] < py[j];
30 }
31 void solve(){
32     for(int i = 0; i <= 1e5; i++) f[i] = i;
33     sort(f + 1, f + n + 1, cmp);
34     memset(bit, 0, sizeof(bit));
35     for(int ii = 1; ii <= n; ii++){
36         int i = f[ii];
37         ll tmp = (sum(1e5) - sum(py[i]) + mod) % mod + 1;
38         tmp %= mod;
39         add(py[i], tmp);
40     }
41     ll ans = sum(1e5) % mod;
42     printf("%I64d
", ans);
43 }
44 int main(){
45     scanf("%d", &n);
46     for(int i = 1; i <= n; i++)
47         scanf("%d %d", &px[i], &py[i]);
48     solve();
49     return 0;
50 }

题目：

Dominant Free Sets

Time limit: 1000 ms
Memory limit: 256 MB

You are given a set $A_x geq B_xAx≥Bx and A_y geq B_yAy≥By. Count the number of non-empty subsets of SS that don't contain two points AA and BB such that AA dominates BB.$

Standard input

The first line contains a single integer

Each of the next

Standard output

Print the answer modulo $10^9+7109+7 on the first line.$

Constraints and notes

$10^51≤N≤105$
$x_i, y_i leq 10^51≤xi,yi≤105$
The

Input	Output	Explanation
4 1 1 2 2 3 3 4 4	4	The only valid sets are the ones with exactly one point.
3 2 1 1 1 1 2	4	The sets are