#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
std::vector<int> y;
int64_t ans;
void solve(int l,int r){
if(r-l==1)
return;
int m=(l+r)>>1;
// ans += number of pairs (i,j) such that l<=i<m, m<=j<r, y[i]<y[j] and there is no point in the rectangle
{
struct pt{int x,y;};
std::vector<pt> is;is.reserve(r-l);
for(int x=l;x<r;++x)
is.push_back({x,y[x]});
std::sort(begin(is),end(is),[](pt a,pt b){return a.y<b.y;});
std::vector<pt> pl; // x<m, visible from current y coord, sorted by decreasing x & increasing y
std::vector<pt> pr; // x>=m, may block point at current y coord, sorted by increasing x & increasing y
for(pt i:is) // sweep over points int increasing y coord direction
if(i.x<m){
while(!pl.empty()&&pl.back().x<i.x)
pl.pop_back();
pl.push_back(i);
}else{
// find point with largest y coord that blocks this point (have x <= this point)
auto iter=std::upper_bound(begin(pr),end(pr),i.x,[](int x,pt p){return x<p.x;});
auto block_y=iter==begin(pr)?INT_MIN:(--iter)->y;
// count number of points int pl with y>block_y
ans+=end(pl)-std::lower_bound(begin(pl),end(pl),block_y,[](pt p,int y){return p.y<y;});
// add this point to pr
while(!pr.empty()&&pr.back().x>i.x)
pr.pop_back();
pr.push_back(i);
}
}
solve(l,m);
solve(m,r);
}
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int n;std::cin>>n;
std::vector<std::pair<int,int>> pts(n);
for(auto& p:pts)std::cin>>p.first>>p.second;
std::sort(begin(pts),end(pts)); // by x
y.resize(n);
std::transform(begin(pts),end(pts),begin(y),[](std::pair<int,int> p){
return p.second;
}); // x coord compression (throw away the information)
pts.clear();
ans=0;
solve(0,n);
std::cout<<ans<<'\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
504 KB |
Output is correct |
| 2 |
Correct |
9 ms |
504 KB |
Output is correct |
| 3 |
Correct |
8 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
632 KB |
Output is correct |
| 5 |
Correct |
8 ms |
504 KB |
Output is correct |
| 6 |
Correct |
9 ms |
504 KB |
Output is correct |
| 7 |
Correct |
9 ms |
504 KB |
Output is correct |
| 8 |
Correct |
6 ms |
504 KB |
Output is correct |
| 9 |
Correct |
8 ms |
504 KB |
Output is correct |
| 10 |
Correct |
9 ms |
504 KB |
Output is correct |
| 11 |
Correct |
9 ms |
504 KB |
Output is correct |
| 12 |
Correct |
7 ms |
504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
211 ms |
7444 KB |
Output is correct |
| 2 |
Correct |
422 ms |
6128 KB |
Output is correct |
| 3 |
Correct |
333 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
227 ms |
7416 KB |
Output is correct |
| 5 |
Correct |
360 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
392 ms |
6436 KB |
Output is correct |
| 7 |
Correct |
404 ms |
6260 KB |
Output is correct |
| 8 |
Correct |
426 ms |
6264 KB |
Output is correct |
| 9 |
Correct |
199 ms |
7436 KB |
Output is correct |
| 10 |
Correct |
361 ms |
6556 KB |
Output is correct |
| 11 |
Correct |
390 ms |
6264 KB |
Output is correct |
| 12 |
Correct |
418 ms |
6264 KB |
Output is correct |
| 13 |
Correct |
421 ms |
6268 KB |
Output is correct |
| 14 |
Correct |
242 ms |
7416 KB |
Output is correct |
| 15 |
Correct |
396 ms |
6436 KB |
Output is correct |
| 16 |
Correct |
420 ms |
6440 KB |
Output is correct |
| 17 |
Correct |
245 ms |
5240 KB |
Output is correct |
| 18 |
Correct |
410 ms |
6444 KB |
Output is correct |
| 19 |
Correct |
409 ms |
6264 KB |
Output is correct |
| 20 |
Correct |
407 ms |
6392 KB |
Output is correct |
