Submission #366495

#	Time	Username	Problem	Language	Result	Execution time	Memory
366495		silverfish	Planine (COCI21_planine)	C++14	110 / 110	525 ms	43760 KiB

Main

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60