oj.uz

Submission #373052

# Submission time Handle Problem Language Result Execution time Memory
373052 2021-03-03T08:10:10 Z sam571128 Planine (COCI21_planine) C++14
20 / 110
 293 ms 43632 KB 
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e6+5;
const double EPS = 1e-7;
pair<double,double> seg[N];
int st[N], id[N];
int n, h;
double findp(int x1, int y1, int x2, int y2){
	assert(y1!=y2);
	return 1.0*(h-y1)*(x2-x1)/(y2-y1)+x1;
}

bool check(pair<double,double> a, pair<double,double> b, pair<double,double> c){
	return (b.second-a.second)*(c.first-a.first) < (c.second-a.second)*(b.first-a.first);
}

signed main(){
	fastio
	//freopen("input.in","r",stdin);
	cin >> n >> h;
	vector<pair<double,double>> v(1);
	for(int i = 1;i <= n;i++){
		int x,y;
		cin >> x >> y;
		v.push_back({x,y});
	}
	vector<int> st;
    for (int i = 1; i <= n; i++) {
    	//dy/dx < dy<dx => (v[st.top()].second-v[i].second)
    	while(st.size() > 2&&check(v[i],v[st[st.size()-1]],v[st[st.size()-2]])) st.pop_back();
        if(i%2==1&&!st.empty()) seg[i].first = findp(v[i].first,v[i].second, v[i-1].first, v[i-1].second);
    	st.push_back(i);
    }
    st.clear();
    for(int i = n; i >= 1; i--) {
    	while(st.size() > 2&&check(v[i],v[st[st.size()-1]],v[st[st.size()-2]])) st.pop_back();
        if(i%2==1&&!st.empty()) seg[i].second = findp(v[i].first,v[i].second, v[i+1].first, v[i+1].second);
    	st.push_back(i);	
    }

    for(int i = 3;i <= n;i++){
    	id[i/2] = i;
    }
    sort(id+1,id+n/2,[&](int a, int b){
    	return seg[a].second < seg[b].second;
    });
    double tmp = seg[id[1]].second;
    int ans = 1;
    for (int i = 1; i <= n / 2 - 1; ++i) {
        if (tmp >= seg[id[i]].first)
            continue;
        //cout << seg[i].first << " " << seg[i].second << "\n";
        tmp = seg[id[i]].second;
        ++ans;
    }
    cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 880 KB Output is correct
2 Correct 3 ms 880 KB Output is correct
3 Correct 3 ms 880 KB Output is correct
4 Correct 26 ms 4836 KB Output is correct
5 Correct 34 ms 4836 KB Output is correct
6 Correct 29 ms 4836 KB Output is correct
7 Correct 250 ms 43580 KB Output is correct
8 Correct 293 ms 43632 KB Output is correct
9 Correct 289 ms 43580 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 880 KB Output is correct
2 Correct 3 ms 880 KB Output is correct
3 Correct 3 ms 880 KB Output is correct
4 Correct 26 ms 4836 KB Output is correct
5 Correct 34 ms 4836 KB Output is correct
6 Correct 29 ms 4836 KB Output is correct
7 Correct 250 ms 43580 KB Output is correct
8 Correct 293 ms 43632 KB Output is correct
9 Correct 289 ms 43580 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Incorrect 1 ms 492 KB Output isn't correct
12 Halted 0 ms 0 KB -