oj.uz

Submission #898593

# Submission time Handle Problem Language Result Execution time Memory
898593 2024-01-04T22:59:57 Z vjudge1 Planine (COCI21_planine) C++17
110 / 110
 498 ms 94468 KB 
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define P complex<ld>
#define X real()
#define Y imag()
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, h;
    cin >> n >> h;
    vector<P> mount(n), ch;
    for(auto &i: mount) {
        ld a, b;
        cin >> a >> b;
        i={a,b};
    }
    vector<pair<ld,ld>> a(n,{-1e18,-1e18});
    for(int i = 1; i < n-1; i++) {
        while(ch.size()>1&&((mount[i]-ch.back())*conj(ch.back()-ch[ch.size()-2])).Y>=0)
            ch.pop_back();
        if(~i&1) {
            P p = mount[i]-ch.back();
            a[i].first=mount[i].X+(p.X/p.Y*(h-mount[i].Y));
        }
        ch.push_back(mount[i]);
    }
    ch.clear();
    for(int i = n-1; --i;) {
        while(ch.size()>1&&((mount[i]-ch.back())*conj(ch.back()-ch[ch.size()-2])).Y<=0)
            ch.pop_back();
        if(~i&1) {
            P p = ch.back()-mount[i];
            a[i].second=mount[i].X+(p.X/p.Y*(h-mount[i].Y));
        }
        ch.push_back(mount[i]);
    }
    vector<pair<ld,ld>> v;
    for(auto i: a)
        if(i.first!=-1e18)
            v.push_back(i);
    sort(v.begin(),v.end());
    int ans = 0;
    ld x = -1e18;
    for(auto i: v) {
        if(i.first-x>1e-10)
            ans++,x=i.second;
        else x=min(x,i.second);
    }
    cout << ans << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1372 KB Output is correct
2 Correct 5 ms 1500 KB Output is correct
3 Correct 5 ms 1488 KB Output is correct
4 Correct 44 ms 9912 KB Output is correct
5 Correct 50 ms 10104 KB Output is correct
6 Correct 49 ms 10192 KB Output is correct
7 Correct 429 ms 91272 KB Output is correct
8 Correct 461 ms 93572 KB Output is correct
9 Correct 463 ms 94468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1372 KB Output is correct
2 Correct 5 ms 1500 KB Output is correct
3 Correct 5 ms 1488 KB Output is correct
4 Correct 44 ms 9912 KB Output is correct
5 Correct 50 ms 10104 KB Output is correct
6 Correct 49 ms 10192 KB Output is correct
7 Correct 429 ms 91272 KB Output is correct
8 Correct 461 ms 93572 KB Output is correct
9 Correct 463 ms 94468 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 435 ms 91640 KB Output is correct
18 Correct 440 ms 91328 KB Output is correct
19 Correct 45 ms 9932 KB Output is correct
20 Correct 435 ms 89932 KB Output is correct
21 Correct 45 ms 9680 KB Output is correct
22 Correct 453 ms 94152 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 442 ms 93432 KB Output is correct
25 Correct 44 ms 9936 KB Output is correct
26 Correct 498 ms 94404 KB Output is correct
27 Correct 22 ms 5104 KB Output is correct