This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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]});
//for (auto it:ranges) cout<<it.fi<<" "<<it.se<<endl;
sort(all(ranges));
double curr=-1e1000;
double eps=1e-9;
int ans=0;
for (auto [l,r]:ranges){
if (curr<l-eps) curr=r,ans++;
else curr=min(curr,r);
}
cout<<ans<<endl;
}
Compilation message (stderr)
Main.cpp:104:2: warning: floating constant exceeds range of 'double' [-Woverflow]
104 | double curr=-1e1000;
| ^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |