Submission #646227

#	Time	Username	Problem	Language	Result	Execution time	Memory
646227		pls33	Mobile (BOI12_mobile)	C++17	0 / 100	633 ms	27472 KiB

mobile

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
    
using namespace std;
using namespace __gnu_pbds;
    
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
    
using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;
    
template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
                        tree_order_statistics_node_update>;
    
template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
                        tree_order_statistics_node_update>;
    
const int BUF_SZ = 1 << 15;
inline namespace fast_in
{
    char buf[BUF_SZ];
    int pos;
    int len;
    
    char next_char(FILE *f)
    {
        if (pos == len)
        {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, f);
    
            if (!len)
            {
                return EOF;
            }
        }
    
        return buf[pos++];
    }
    
    int read_int(FILE *f)
    {
        int x;
        char ch;
        int sgn = 1;
    
        while (!isdigit(ch = next_char(f)))
        {
            if (ch == '-')
            {
                sgn *= -1;
            }
        }
    
        x = ch - '0';
        while (isdigit(ch = next_char(f)))
        {
            x = x * 10 + (ch - '0');
        }
    
        return x * sgn;
    }
}
    
/**
 * @brief gale programos flush_out kviest!!
 */
inline namespace fast_out
{
    char buf[BUF_SZ];
    int pos;
    
    void flush_out(FILE *f)
    {
        fwrite(buf, 1, pos, f);
        pos = 0;
    }
    
    void write_char(char c, FILE *f)
    {
        if (pos == BUF_SZ)
        {
            flush_out(f);
        }
    
        buf[pos++] = c;
    }
    
    void write_int(int x, FILE *f)
    {
        static char num_buf[100];
    
        if (x < 0)
        {
            write_char('-', f);
            x *= -1;
        }
    
        int len = 0;
        for (; x >= 10; x /= 10)
        {
            num_buf[len++] = (char)('0' + (x % 10));
        }
    
        write_char((char)('0' + x), f);
        while (len)
        {
            write_char(num_buf[--len], f);
        }
        write_char('\n', f);
    }
}
#pragma endregion

using fl_t = long double;
const fl_t __eps = 1e-3; 

struct line_t
{
    int64_t m, c;
    long long eval(long long x) const { return m * x + c; }
    fl_t eval_fl(fl_t x) const { return m * x + c; }
    
    fl_t intersect(line_t line){
        fl_t diff_c = c - line.c;
        fl_t diff_m = line.m - m;

        return diff_c / diff_m;
    }
};

fl_t equal(fl_t a, fl_t b){
    return fabsl(a - b) < __eps;
}

struct cht_t
{
    deque<line_t> hull;
    vector<fl_t> ints;
    function<bool(int, int)> compare;

    cht_t(int size): ints(size, 0.0)
    {
        iota(ints.begin(), ints.end(), 0.0);
        //hull.push_front({0, 0});

        compare = [this](int index, int x){
            return this->hull[index].intersect(this->hull[index + 1]) < x;
        };
    }
    
    void add(int64_t m, int64_t c){
        line_t line = {m, c};

        fl_t int_a = line.intersect(hull[0]);
        fl_t int_b = hull[0].intersect(hull[1]);

        while(hull.size() >= 2 && ((int_a > int_b) || equal(int_a, int_b))){
            hull.pop_front();
        }

        hull.push_front(line);
    }

    fl_t query(fl_t x){

        int index = *lower_bound(ints.begin(), ints.begin() + hull.size() - 1, x, compare);
        return hull[index].eval_fl(x);
    }
};
    
void add(p32 a, cht_t &cht)
{
    int64_t m = -2ll * a.first;
    int64_t c = (int64_t)a.first * a.first + (int64_t)a.second * a.second;
    
    cht.add(-m, -c);
}

fl_t query(fl_t x, cht_t &cht){
    return -cht.query(x) + x * x;
}

fl_t ternary_search(fl_t l, fl_t r, cht_t &cht){
    while(r - l > __eps){
        fl_t m1 = l + (r - l) / 3;
        fl_t m2 = r - (r - l) / 3;

        if(query(m1, cht) < query(m2, cht)){
            l = m1;
        }
        else {
            r = m2;
        }
    }

    return query(l, cht);
}
    
int main()
{
    //freopen("mobile.in", "r", stdin);
    
    int n, length;
    cin >> n >> length;
    
    vp32 station(n);
    
    cht_t cht(n);
    for (auto &s : station)
    {
        cin >> s.first >> s.second;
    
        add(s, cht);
    }
    
    cout << sqrt(ternary_search(0.0, length, cht)) << '\n';
    
    return 0;
}

Compilation message (stderr)

mobile.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
mobile.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      |

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5