oj.uz

Submission #366495

# Submission time Handle Problem Language Result Execution time Memory
366495 2021-02-14T09:27:31 Z silverfish Planine (COCI21_planine) C++14
110 / 110
 525 ms 43760 KB 
#include <bits/stdc++.h>
using namespace std;

/*<DEBUG>*/
#define tem template <typename 
#define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i)
#define _op debug& operator<<
tem C > auto test(C *x) -> decltype(cerr << *x, 0LL);
tem C > char test(...);
tem C > struct itr{C begin, end; };
tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }
struct debug{
#ifdef _LOCAL
	~debug(){ cerr << endl; }
	tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; }
	tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); }
	tem T, typename U > _op (pair<T, U> i){ 
		return *this << "< " << i.first << " , " << i.second << " >"; }
	tem T> _op (itr<T> i){
		*this <<  "{ ";
		for(auto it = i.begin; it != i.end; it++){
			*this << " , " + (it==i.begin?2:0) << *it;
		}
		return *this << " }";
	}
#else
tem T> _op (const T&) { return *this; }
#endif 
};

string _ARR_(int* arr, int sz){
	string ret = "{ " + to_string(arr[0]); 
	for(int i = 1; i < sz; i++) ret += " , " +  to_string(arr[i]);
	ret += " }"; return ret;
}

#define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]"
/*</DEBUG>*/

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef long double ld;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array

const int INF = 1e9 + 7, N = 1e6 + 1;

int vis[N];

struct point{
	ll p1, p2;
	int id;
	bool start;

	bool operator==(const point &a){
		return p1*a.p2 == p2*a.p1;
	}
	bool operator!=(const point &a){
		return p1*a.p2 != p2*a.p1;
	}
};

struct r_point{
	ll x, y;

	r_point operator-(const r_point &a){
		return {x - a.x, y - a.y};
	}
};

int turn(r_point a, r_point b){
	ll s = a.x*b.y - a.y*b.x;
	return (s > 0) - (s < 0);
}

int turn(r_point a, r_point b, r_point c){
	return turn(b-a, c-a);
}

vector<point> points;
r_point p[N];

int main(void)
{
	FAST;
	ll h;
	int n; cin >> n >> h;

	for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;

	int l;
	ll lx, ly;
	vector<r_point> hull;

	for(int i = 3; i <= n-2; i+=2){
		ll x = p[i].x, y = p[i].y; 

		while(hull.size() >= 2 && turn(p[i-1], hull.back(), hull[hull.size()-2]) <= 0) hull.pop_back();
		hull.pb(p[i-1]);

		if(hull.size() == 1 || turn(p[i], hull[1], hull[0]) <= 0) l = 0;
		else{
			l = hull.size() - 1;
			for(int j = 22; j >= 0; --j){
				if(l - (1<<j) > 0 && turn(p[i], hull[l-(1<<j)], hull[l - (1<<j) -1]) <= 0) l-=(1<<j);
			}
			if(turn(p[i], hull[l], hull[l-1]) <= 0) --l;
		}

		lx = hull[l].x;
		ly = hull[l].y;

		points.pb({(h - y)*(lx-x) + x*(ly-y), ly-y, i, 1});
	}

	hull.clear();

	for(int i = n-2; i >= 3; i -= 2){
		ll x = p[i].x, y = p[i].y;	

		while(hull.size() >= 2 && turn(p[i+1], hull.back(), hull[hull.size()-2]) >= 0) hull.pop_back();
		hull.pb(p[i+1]); 

		if(hull.size() == 1 || turn(p[i], hull[1], hull[0]) >= 0) l = 0;
		else{
			l = hull.size() - 1;
			for(int j = 22; j >= 0; --j){
				if(l - (1<<j) > 0 && turn(p[i], hull[l-(1<<j)], hull[l - (1<<j) -1]) >= 0) l-=(1<<j);
			}
			if(turn(p[i], hull[l], hull[l-1]) >= 0) --l;
		}

		lx = hull[l].x;
		ly = hull[l].y;

		points.pb({(h-y)*(lx-x) + x*(ly-y), ly-y, i, 0});
	}

	auto cmp = [](const point &a, const point &b){
		if(a.p1*b.p2==a.p2*b.p1) return a.id < b.id;
		return a.p1*b.p2 < a.p2*b.p1;
	};

	sort(points.begin(), points.end(), cmp);

	stack<int> cur;
	int ans = 0;
	bool clear = 0;

	for(int i = 0; i < (int)points.size(); ++i){

		if(clear && (i == (int)points.size()-1 || points[i] != points[i+1])){
			clear = 0;
			++ans;
			vis[points[i].id] = 1;
			while(cur.size()){
				vis[cur.top()] = 1;
				cur.pop();
			}
			continue;
		}

		if(points[i].start){
			cur.push(points[i].id);
		}else{

			if(i < (int)points.size()-1 && !vis[points[i].id] && points[i] == points[i+1]) clear = 1;
			if(clear) continue;

			if(!vis[points[i].id]){
				++ans;
				vis[points[i].id] = 1;
				while(cur.size()){
					vis[cur.top()] = 1;
					cur.pop();
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1068 KB Output is correct
2 Correct 4 ms 1068 KB Output is correct
3 Correct 4 ms 1068 KB Output is correct
4 Correct 44 ms 5088 KB Output is correct
5 Correct 42 ms 5088 KB Output is correct
6 Correct 41 ms 5088 KB Output is correct
7 Correct 452 ms 43556 KB Output is correct
8 Correct 483 ms 43556 KB Output is correct
9 Correct 450 ms 43556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1068 KB Output is correct
2 Correct 4 ms 1068 KB Output is correct
3 Correct 4 ms 1068 KB Output is correct
4 Correct 44 ms 5088 KB Output is correct
5 Correct 42 ms 5088 KB Output is correct
6 Correct 41 ms 5088 KB Output is correct
7 Correct 452 ms 43556 KB Output is correct
8 Correct 483 ms 43556 KB Output is correct
9 Correct 450 ms 43556 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 459 ms 43556 KB Output is correct
18 Correct 498 ms 43636 KB Output is correct
19 Correct 44 ms 5092 KB Output is correct
20 Correct 490 ms 43520 KB Output is correct
21 Correct 43 ms 5092 KB Output is correct
22 Correct 525 ms 43492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 519 ms 43516 KB Output is correct
25 Correct 43 ms 5088 KB Output is correct
26 Correct 454 ms 43760 KB Output is correct
27 Correct 19 ms 2788 KB Output is correct