#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; ++i)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int MX = 200005, INF = 2000020000;
ll ans;
P in[MX];
struct bit {
vector<int> d;
bit(int n):d(n+5,0){}
void add(int i){ while(i < d.size()) ++d[i], i += i&-i;}
int sum(int i){ int res = 0; while(i) res += d[i], i -= i&-i; return res;}
};
void f(P p[], int n){
if(n <= 1) return;
int c = n/2;
f(p,c); f(p+c,n-c);
set<int> s;
vector<P> l, r; // cover range
s.insert(INF);
for(int i = c-1; i >= 0; --i){
int x = *(s.lower_bound(p[i].se));
l.push_back(P(p[i].se,x-1));
s.insert(p[i].se);
}
s.clear(); s.insert(INF);
for(int i = c; i < n; ++i){
int x = -(*(s.lower_bound(-p[i].se)));
r.push_back(P(x+1,p[i].se));
s.insert(-p[i].se);
}
sort(l.begin(),l.end());
sort(r.begin(),r.end());
map<int,int> z; // compress axis
rep(i,l.size()){
z.insert(P(l[i].fi,0));
z.insert(P(l[i].se,0));
}
rep(i,r.size()){
z.insert(P(r[i].fi,0));
z.insert(P(r[i].se,0));
}
int k = 1;
for(map<int,int>::iterator it = z.begin(); it != z.end(); ++it) it->se = k++;
bit d(k);
// valid pair : R.first <= L.first <= R.second <= L.second
k = 0;
rep(i,l.size()){
while(k < r.size() && r[k].fi <= l[i].fi) d.add(z[r[k++].se]);
ans += d.sum(z[l[i].se])-d.sum(z[l[i].fi]-1);
}
}
int main(){
int n;
scanf("%d",&n);
rep(i,n) scanf("%d%d",&in[i].fi,&in[i].se);
sort(in,in+n);
f(in,n);
printf("%lld\n",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
3212 KB |
Output is correct |
| 2 |
Correct |
44 ms |
3368 KB |
Output is correct |
| 3 |
Correct |
40 ms |
3276 KB |
Output is correct |
| 4 |
Correct |
28 ms |
3428 KB |
Output is correct |
| 5 |
Correct |
40 ms |
3352 KB |
Output is correct |
| 6 |
Correct |
44 ms |
3348 KB |
Output is correct |
| 7 |
Correct |
40 ms |
3368 KB |
Output is correct |
| 8 |
Correct |
28 ms |
3212 KB |
Output is correct |
| 9 |
Correct |
36 ms |
3212 KB |
Output is correct |
| 10 |
Correct |
36 ms |
3352 KB |
Output is correct |
| 11 |
Correct |
40 ms |
3268 KB |
Output is correct |
| 12 |
Correct |
28 ms |
3148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2192 ms |
19696 KB |
Output is correct |
| 2 |
Correct |
2940 ms |
24780 KB |
Output is correct |
| 3 |
Correct |
2568 ms |
24728 KB |
Output is correct |
| 4 |
Correct |
2396 ms |
29752 KB |
Output is correct |
| 5 |
Correct |
2684 ms |
27316 KB |
Output is correct |
| 6 |
Correct |
2760 ms |
25292 KB |
Output is correct |
| 7 |
Correct |
2892 ms |
24840 KB |
Output is correct |
| 8 |
Correct |
2972 ms |
24748 KB |
Output is correct |
| 9 |
Correct |
2208 ms |
19696 KB |
Output is correct |
| 10 |
Correct |
2252 ms |
22132 KB |
Output is correct |
| 11 |
Correct |
2420 ms |
24096 KB |
Output is correct |
| 12 |
Correct |
2716 ms |
24516 KB |
Output is correct |
| 13 |
Correct |
2880 ms |
24656 KB |
Output is correct |
| 14 |
Correct |
2036 ms |
20272 KB |
Output is correct |
| 15 |
Correct |
2460 ms |
24084 KB |
Output is correct |
| 16 |
Correct |
2904 ms |
24656 KB |
Output is correct |
| 17 |
Correct |
1708 ms |
16832 KB |
Output is correct |
| 18 |
Correct |
2904 ms |
24704 KB |
Output is correct |
| 19 |
Correct |
2856 ms |
24660 KB |
Output is correct |
| 20 |
Correct |
2864 ms |
24740 KB |
Output is correct |
