oj.uz

Submission #367081

# Submission time Handle Problem Language Result Execution time Memory
367081 2021-02-16T07:24:02 Z CodePlatina Planine (COCI21_planine) C++14
110 / 110
 365 ms 32224 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tlll tuple<long long, long long, long long>
#define tiiii tuple<int, int, int, int>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
//#define DEBUG

using namespace std;

const long long INF = (long long)8e18;

struct Frac
{
    long long up, dn;

    Frac(void) : up(0), dn(1) {}
    Frac(long long x, long long y) : up(x), dn(y) { if(dn < 0) up = -up, dn = -dn; }

    bool operator< (const Frac &ot) const { return up * ot.dn < ot.up * dn; }
};

struct Line
{
    long long a, b;

    Frac eval(Frac x) { return Frac(a * x.up + b * x.dn, x.dn); }
    Frac cross(const Line &ot) const { return Frac(b - ot.b, ot.a - a); }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, h; cin >> n >> h;
    pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;

    int N = (n - 3) / 2;
    if(N == 0) { cout << 0; return 0; }
    pair<Frac, Frac> ran[N];

    vector<Line> ln;
    for(int i = 1; i < n - 1; ++i)
    {
        if(i & 1)
        {
            Line x{A[i].ff, A[i].ss};
            while(ln.size() >= 2 && x.cross(ln.back()) < x.cross(ln[(int)ln.size() - 2])) ln.pop_back();
            ln.push_back(x);
        }

        else
        {
            Line x{A[i].ff, A[i].ss};
            int s = 0, e = (int)ln.size();
            while(s + 1 < e)
            {
                int mid = s + e >> 1;
                Frac cr = ln[mid].cross(ln[mid - 1]);
                if(x.eval(cr) < ln[mid].eval(cr)) s = mid;
                else e = mid;
            }
            Frac tmp = x.cross(ln[s]);
            ran[i / 2 - 1].ff = Frac(A[i].ff * tmp.up - (h - A[i].ss) * tmp.dn, tmp.up);
        }
    }

    ln.clear();
    for(int i = n - 2; i >= 1; --i)
    {
        if(i & 1)
        {
            Line x{-A[i].ff, A[i].ss};
            while(ln.size() >= 2 && x.cross(ln.back()) < x.cross(ln[(int)ln.size() - 2])) ln.pop_back();
            ln.push_back(x);
        }

        else
        {
            Line x{-A[i].ff, A[i].ss};
            int s = 0, e = (int)ln.size();
            while(s + 1 < e)
            {
                int mid = s + e >> 1;
                Frac cr = ln[mid].cross(ln[mid - 1]);
                if(x.eval(cr) < ln[mid].eval(cr)) s = mid;
                else e = mid;
            }
            Frac tmp = x.cross(ln[s]);
            ran[i / 2 - 1].ss = Frac(A[i].ff * tmp.up + (h - A[i].ss) * tmp.dn, tmp.up);
        }
    }

    #ifdef DEBUG
        cout << endl;
        cout << "ran" << endl;
        for(int i = 0; i < N; ++i)
        {
            cout << "{ " << ran[i].ff.up << " / " << ran[i].ff.dn << " }, ";
            cout << "{ " << ran[i].ss.up << " / " << ran[i].ss.dn << " }\n";
        }
        cout << endl;
    #endif

    using pff = pair<Frac, Frac>;

    sort(ran, ran + N, [](pff x, pff y){ return x.ss < y.ss; });

    int ans = 1; Frac mn = ran[0].ss;
    for(int i = 1; i < N; ++i)
    {
        if(mn < ran[i].ff)
            ++ans, mn = ran[i].ss;
    }
    cout << ans;

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:70:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |                 int mid = s + e >> 1;
      |                           ~~^~~
Main.cpp:96:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |                 int mid = s + e >> 1;
      |                           ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 27 ms 3820 KB Output is correct
5 Correct 29 ms 3820 KB Output is correct
6 Correct 31 ms 3820 KB Output is correct
7 Correct 290 ms 32224 KB Output is correct
8 Correct 365 ms 32132 KB Output is correct
9 Correct 331 ms 32160 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 4 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 27 ms 3820 KB Output is correct
5 Correct 29 ms 3820 KB Output is correct
6 Correct 31 ms 3820 KB Output is correct
7 Correct 290 ms 32224 KB Output is correct
8 Correct 365 ms 32132 KB Output is correct
9 Correct 331 ms 32160 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 333 ms 32136 KB Output is correct
18 Correct 286 ms 23916 KB Output is correct
19 Correct 27 ms 2668 KB Output is correct
20 Correct 263 ms 23788 KB Output is correct
21 Correct 25 ms 2668 KB Output is correct
22 Correct 265 ms 23828 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 275 ms 23916 KB Output is correct
25 Correct 36 ms 2668 KB Output is correct
26 Correct 313 ms 23916 KB Output is correct
27 Correct 13 ms 1772 KB Output is correct