oj.uz

Submission #373054

# Submission time Handle Problem Language Result Execution time Memory
373054 2021-03-03T08:13:17 Z sam571128 Planine (COCI21_planine) C++14
110 / 110
 321 ms 54608 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[st.back()].first, v[st.back()].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[st.back()].first, v[st.back()].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 26 ms 4836 KB Output is correct
6 Correct 29 ms 4836 KB Output is correct
7 Correct 252 ms 43580 KB Output is correct
8 Correct 265 ms 43580 KB Output is correct
9 Correct 302 ms 43580 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #3
60.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 26 ms 4836 KB Output is correct
6 Correct 29 ms 4836 KB Output is correct
7 Correct 252 ms 43580 KB Output is correct
8 Correct 265 ms 43580 KB Output is correct
9 Correct 302 ms 43580 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 257 ms 54608 KB Output is correct
18 Correct 263 ms 46652 KB Output is correct
19 Correct 27 ms 5092 KB Output is correct
20 Correct 265 ms 45756 KB Output is correct
21 Correct 27 ms 5092 KB Output is correct
22 Correct 285 ms 49596 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 269 ms 48908 KB Output is correct
25 Correct 27 ms 5220 KB Output is correct
26 Correct 321 ms 49908 KB Output is correct
27 Correct 13 ms 2792 KB Output is correct