oj.uz

Submission #382796

# Submission time Handle Problem Language Result Execution time Memory
382796 2021-03-28T08:24:20 Z ne4eHbKa Planine (COCI21_planine) C++17
110 / 110
 353 ms 37868 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 1e6 + 5;
int h, x[N], y[N], n;
vector<pair<ld, ld>> c;
vector<int> f;

ld point(int i, int j) { return x[j] + ld(x[j] - x[i]) / (y[j] - y[i]) * (h - y[j]); }

const ld eps = 1e-15;
inline bool eq(const ld a, const ld b) {return abs(a - b) < eps;}
inline bool le(const ld a, const ld b) {return a + eps < b;}

ll s(int a, int b, int c) { return (x[b] - x[a]) * ll(y[c] - y[a]) - (y[b] - y[a]) * ll(x[c] - x[a]); }

void solve() {
    cin >> n >> h;
    for(int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
    c.resize(n - 3 >> 1);
    int i = 0;
    for(int j = 0; j < n; ++j) {
        while(len(f) > 1) {
            int pr = f.back();
            int pr2 = f[len(f) - 2];
            if(s(pr2, pr, j) < 0)
                break;
            f.pop_back();
        }
        if(!(j & 1) && j && j + 1 < n)
            c[i++].ft = point(j, f.back());
        f.push_back(j);
    }
    i = len(c) - 1;
    for(int j = n - 1; ~j; --j) {
        while(len(f) > 1) {
            int pr = f.back();
            int pr2 = f[len(f) - 2];
            if(s(pr2, pr, j) > 0)
                break;
            f.pop_back();
        }
        if(!(j & 1) && j && j + 1 < n)
            c[i--].sd = point(j, f.back());
        f.push_back(j);
    }
    sort(bnd(c));
    n = len(c);
    for(int i = n - 2; i >= 0; --i)
        umin(c[i].sd, c[i + 1].sd);
    int ans {};
    bool u = true;
    ld z;
    for(int i = 0; i < n; ++i) {
        if(u || le(z, c[i].ft))
            z = c[i].sd,
            ++ans,
            u = false;
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:47:16: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   47 |     c.resize(n - 3 >> 1);
      |              ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 4 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 26 ms 2668 KB Output is correct
5 Correct 32 ms 2852 KB Output is correct
6 Correct 31 ms 2668 KB Output is correct
7 Correct 270 ms 23916 KB Output is correct
8 Correct 293 ms 23892 KB Output is correct
9 Correct 306 ms 23884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 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 4 ms 620 KB Output is correct
2 Correct 4 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 26 ms 2668 KB Output is correct
5 Correct 32 ms 2852 KB Output is correct
6 Correct 31 ms 2668 KB Output is correct
7 Correct 270 ms 23916 KB Output is correct
8 Correct 293 ms 23892 KB Output is correct
9 Correct 306 ms 23884 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 280 ms 34924 KB Output is correct
18 Correct 283 ms 34668 KB Output is correct
19 Correct 29 ms 3948 KB Output is correct
20 Correct 286 ms 34028 KB Output is correct
21 Correct 29 ms 3692 KB Output is correct
22 Correct 294 ms 37612 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 298 ms 36844 KB Output is correct
25 Correct 29 ms 3820 KB Output is correct
26 Correct 353 ms 37868 KB Output is correct
27 Correct 16 ms 2156 KB Output is correct