oj.uz

답안 #536652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536652 2022-03-13T16:52:03 Z errorgorn Planine (COCI21_planine) C++17
30 / 110
 2000 ms 2100 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 hval(int i,int j){
	return arr[i].fi+(h-arr[i].se)*slope(i,j);
}

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;
	
	#define dd pair<double,double>
	vector<dd> ranges;
	
	for (int x=3;x<=n-2;x+=2){
		dd temp=dd(-1e100,1e100);
		rep(y,1,n+1){
			if (arr[y].fi<arr[x].fi && arr[y].se>arr[x].se) temp.fi=max(temp.fi,hval(x,y));
			if (arr[y].fi>arr[x].fi && arr[y].se>arr[x].se) temp.se=min(temp.se,hval(x,y));
		}
		ranges.pub(temp);
	}
	
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 628 KB Output is correct
2 Correct 238 ms 708 KB Output is correct
3 Correct 240 ms 628 KB Output is correct
4 Execution timed out 2086 ms 2100 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 12 ms 388 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 10 ms 428 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 628 KB Output is correct
2 Correct 238 ms 708 KB Output is correct
3 Correct 240 ms 628 KB Output is correct
4 Execution timed out 2086 ms 2100 KB Time limit exceeded
5 Halted 0 ms 0 KB -