oj.uz

Submission #536642

# Submission time Handle Problem Language Result Execution time Memory
536642 2022-03-13T16:17:31 Z errorgorn Planine (COCI21_planine) C++17
0 / 110
 2000 ms 2504 KB 
// 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]>=arr[idx.back()]) idx.pob();
			while (sz(idx)>=2 && slope(x,idx.back())<=slope(idx.back(),idx[sz(idx)-2])) idx.pob();
			idx.pub(x);
		}
		else{
			while (sz(idx)>=2 && hval(x,idx.back())>=hval(x,idx[sz(idx)-2])) idx.pob();
			//res.pub(hval(x,idx.back()));
		
			double temp=1e100;
			for (int y=x+1;y<n;y+=2) if (arr[x].se<arr[y].se) temp=min(temp,hval(x,idx.back()));
			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,sz(temp)-1) 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 708 KB Output is correct
2 Correct 63 ms 748 KB Output is correct
3 Correct 62 ms 664 KB Output is correct
4 Execution timed out 2069 ms 2504 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Incorrect 4 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 708 KB Output is correct
2 Correct 63 ms 748 KB Output is correct
3 Correct 62 ms 664 KB Output is correct
4 Execution timed out 2069 ms 2504 KB Time limit exceeded
5 Halted 0 ms 0 KB -