Submission #156083

#	Time	Username	Problem	Language	Result	Execution time	Memory
156083		user202729	허수아비 (JOI14_scarecrows)	C++17	100 / 100	426 ms	7444 KiB

scarecrows

#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';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85