Submission #536657

#	Time	Username	Problem	Language	Result	Execution time	Memory
536657		errorgorn	Planine (COCI21_planine)	C++17	110 / 110	244 ms	46156 KiB

Main

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,h;
ii arr[1000005];

double slope(int i,int j){
	return (double)(arr[j].fi-arr[i].fi)/(arr[j].se-arr[i].se);
}

double inter(int i,int j){
	return arr[i].fi-arr[i].se*slope(i,j);
}

double hval(int i,int j){
	return arr[i].fi+(h-arr[i].se)*slope(i,j);
}

vector<double> solve(){
	vector<double> res={1e100};
	
	vector<int> idx;
	
	rep(x,n,1){
		if (x%2==0){
			while (!idx.empty() && arr[x].se>=arr[idx.back()].se) idx.pob();
			while (sz(idx)>=2 && slope(x,idx.back())>=slope(idx.back(),idx[sz(idx)-2])) idx.pob();
			idx.pub(x);
		}
		else{
			double temp=1e100;
			for (auto it:idx) temp=min(temp,hval(x,it));
			res.pub(temp);
		}
	}
	
	reverse(all(res));
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>h;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	
	auto temp=solve();
	reverse(arr+1,arr+n+1);
	rep(x,1,n+1) arr[x].fi=-arr[x].fi;
	auto temp2=solve();
	
	reverse(all(temp2));
	
	#define dd pair<double,double>
	vector<dd> ranges;
	
	rep(x,1,(n-1)/2) ranges.pub({-temp2[x],temp[x]});
	
	sort(all(ranges));
	double curr=-1e100;
	
	int ans=0;
	for (auto [l,r]:ranges){
		if (curr<l) curr=r,ans++;
		else curr=min(curr,r);
	}
	
	cout<<ans<<endl;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60