oj.uz

Submission #156083

# Submission time Handle Problem Language Result Execution time Memory
156083 2019-10-03T08:16:16 Z user202729 허수아비 (JOI14_scarecrows) C++17
100 / 100
 426 ms 7444 KB 
#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.0 / 5.0

# Verdict Execution time Memory 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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory 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