oj.uz

Submission #370954

# Submission time Handle Problem Language Result Execution time Memory
370954 2021-02-25T08:21:09 Z neki Planine (COCI21_planine) C++14
110 / 110
 881 ms 91096 KB 
#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;i++)
#define pool(i, a, b) for(ll i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 500100
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007

ll vecpro(par s, par p1, par p2){
    p1.fi-=s.fi;p1.se-=s.se;
    p2.fi-=s.fi;p2.se-=s.se;
    return p1.fi * p2.se - p2.fi * p1.se;
}
 
par inter(par p1, par p2, ll h){return make_pair(((h-p1.se) * (p2.fi - p1.fi) + p1.fi * (p2.se - p1.se)) , (p2.se - p1.se)) ;}
 
vc<par> gt(vc<par> a, ll h ){
    ll n=a.size();
    vc<par> st; 
    vc<par> ret;
    
    for(ll i=1;i<n;i+=2){
        while(st.size()>=2 and vecpro(st[st.size()-1],  st[st.size()-2], a[i-1])<0) st.pop_back();
        st.ps(a[i-1]);
        while(st.size()>=2 and vecpro(st[st.size()-1],  st[st.size()-2], a[i])<0) st.pop_back();
        ret.ps(inter(st.back(), a[i], h));
        //cout << st.back().fi<<" "<<st.back().se<<" "<<a[i].fi<<" "<<a[i].se <<" "<<inter(st.back(), a[i], h)<<endl;
    }
    return ret;
}

ll qcmp(par a, par b){return a.fi * b.se < a.se * b.fi;}
ll cmp(pair<par, par> a, pair<par, par> b){
    return qcmp(a.fi, b.fi);
}

int main() {
    ll n, h;cin >> n>>h;
    vc<par> poi;
    loop(i, 0, n){
        ll x, y;cin >> x >> y;
        if(i!=0 and i!=n-1)poi.ps(make_pair(x, y));
    }
    
    vc<par> a=gt(poi, h);
    fore(v, a) if(v.se<0) v.fi*=-1, v.se*=-1;
    
    reverse(all(poi));
    fore(v, poi) v.fi=-v.fi;
    vc<par> b=gt(poi, h);
    fore(v, b) v.fi=-v.fi;
    fore(v, b) if(v.se<0) v.fi*=-1, v.se*=-1;
    reverse(all(b));
    
    n=a.size();
    vc<pair<par, par>> ints;
    loop(i, 0, n)  ints.ps(make_pair(a[i], b[i]));
    
    sort(all(ints), cmp);
    
    //loop(i, 0, n) cout << ints[i].fi << " "<< ints[i].se<<endl;
    
    par cur=make_pair(llmax, -1); ll ans=0;
    pool(i, n, 0){
        if(cur.fi==llmax or qcmp(ints[i].se, cur)) ans++, cur=ints[i].fi;
    }
    cout << ans<<endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1164 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 10 ms 1144 KB Output is correct
4 Correct 71 ms 9792 KB Output is correct
5 Correct 78 ms 9920 KB Output is correct
6 Correct 86 ms 10304 KB Output is correct
7 Correct 738 ms 87300 KB Output is correct
8 Correct 798 ms 89060 KB Output is correct
9 Correct 860 ms 91096 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 2 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 0 ms 364 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1164 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 10 ms 1144 KB Output is correct
4 Correct 71 ms 9792 KB Output is correct
5 Correct 78 ms 9920 KB Output is correct
6 Correct 86 ms 10304 KB Output is correct
7 Correct 738 ms 87300 KB Output is correct
8 Correct 798 ms 89060 KB Output is correct
9 Correct 860 ms 91096 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 758 ms 88076 KB Output is correct
18 Correct 800 ms 86404 KB Output is correct
19 Correct 74 ms 8768 KB Output is correct
20 Correct 730 ms 81292 KB Output is correct
21 Correct 78 ms 8640 KB Output is correct
22 Correct 834 ms 89100 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 818 ms 84236 KB Output is correct
25 Correct 74 ms 8768 KB Output is correct
26 Correct 881 ms 85548 KB Output is correct
27 Correct 41 ms 4560 KB Output is correct