Submission #951142

#	Time	Username	Problem	Language	Result	Execution time	Memory
951142		Kavelmydex	Mobile (BOI12_mobile)	C++17	0 / 100	492 ms	49068 KiB

mobile

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define vi vector<int>
#define rep(i,x,n) for(int i=x; i<n; ++i)
#define For(i,n) rep(i,0,n)
#define endl "\n"
#define sp ' '
#define pb push_back
#define f first
#define s second
#define sz size()
#define all(x) (x).begin(),(x).end()
 
const int N = 2e5+1, OO = 1e18, mod = 1e9;
void tr(int a, int b){cout << a << sp << b << endl;}
void cmx(double &a, double b){a = max(a,b);}
void cmn(double &a, double b){a = min(a,b);}

pi p[N];
deque <pi> v, u;
int n,l; 
int fun(int j){
    if(u.sz == 1) return j ? -OO: OO;
    int X = abs(u[0].f - u[1].f);
    int d = ( u[0].s * u[0].s - u[1].s * u[1].s + X * X ) / (-2*X);
    return d;
}
void deb(){
    deque <pi> t;
    For(i,n){
        int j = i, mn = OO;
        while(j < n && v[i].f == v[j].f) mn = min(mn, v[j].s), j++;
        t.pb(v[i]);
        i = j-1;
    }
    v = t; n = v.sz;
}
int32_t main() {
    // ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    For(i,n){
        int x,y; cin >> x >> y;
        y = abs(y);
        v.pb({x,y});
    }
    deb();
    int bst = OO;
    For(i,n){
        auto [x,y] = v[i];
        while(u.sz > 1 && bst + u.front().f < x){
            u.pop_front(); 
            while(bst = fun(0) < 0) u.pop_front();
        }
        while(u.sz && u.back().s * u.back().s >= (abs(x-u.back().f)*abs(x-u.back().f) + y*y)) u.pop_back();
        if(u.sz && abs(u.front().f-x) * abs(u.front().f-x) + u.front().s * u.front().s <= y*y){
            u.pb(v[i]);
        } else {
            u.clear(); 
            u.pb(v[i]);
        }
        p[i] = u.front();
    }
    double mn1 = OO, mn2 = OO, ans = 0;
    for(auto [x,y]: v){
        cmn(mn1, x*x+y*y);
        cmn(mn2, abs(x-l)*abs(x-l)+y*y);
    }
    cmx(ans, max(mn1,mn2));
    bst = -OO;
    for(int i=n-1; i>=1; --i){
        auto [x,y] = v[i];
        while(u.sz > 1 && -bst + u.front().f > x){
            u.pop_front(); 
            while(bst = fun(1) > 0) u.pop_front();
        }
        while(u.sz && u.back().s * u.back().s >= (abs(x-u.back().f)*abs(x-u.back().f) + y*y)) u.pop_back();
        if(u.sz && abs(u.front().f-x) * abs(u.front().f-x) + u.front().s * u.front().s <= y*y){
            u.pb(v[i]);
        }else {
            u.clear(); 
            u.pb(v[i]);
        }
        pi L = p[i-1], R = u.front();
        double X = abs(R.f - L.f);
        double d = ( R.s * R.s - L.s * L.s + X*X ) / (2*X);
        if(R.f >= 0 && L.f >= 0){
            cmx(ans, sqrt(d*d + L.s*L.s));           
        }
        if(R.f > l && L.f <= l){
            cmx(ans, min(mn2,sqrt(d*d + L.s * L.s)));
        }
        if(L.f < 0 && R.f >= 0){
            cmx(ans, min(mn2,sqrt(d*d + L.s * L.s)));
        }
    }
    cout << fixed << setprecision(4) << ans << endl;
    return 0;
}

Compilation message (stderr)

mobile.cpp: In function 'int32_t main()':
mobile.cpp:54:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   54 |             while(bst = fun(0) < 0) u.pop_front();
      |                   ~~~~^~~~~~~~~~~~
mobile.cpp:76:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   76 |             while(bst = fun(1) > 0) u.pop_front();
      |                   ~~~~^~~~~~~~~~~~

• 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