oj.uz

답안 #240725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240725 2020-06-21T01:04:46 Z WhaleVomit Lightning Conductor (POI11_pio) C++14
100 / 100
 822 ms 24984 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
 
#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)
 
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
 
const int MAX_N = 500500;
int n;
 
ld eval(ld x, pair<ll,ll> curve) {
    return curve.s + sqrt(curve.f - x);
}
 
ll evalLong(ll x, pair<ll,ll> curve) { // ceil(eval(x, curve))
    ld y = eval(x,curve);
    ll y1 = y;
    if((y1-curve.s)*(y1-curve.s) >= curve.f-x) return y1;
    return y1+1;
}
 
ld intersect(pair<ll,ll> c1, pair<ll,ll> c2) { // c2 comes after c1
    if(eval(c1.f, c2) <= c1.s) return c1.f;
    if(eval(0, c2) >= eval(0, c1)) return -1;
    ld lo = 0;
    ld hi = c1.f;
    while(hi-lo > 1e-8) {
        ld mid = (lo + hi)/2;
        if(eval(mid, c1) < eval(mid, c2)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    assert(0 <= lo && lo < c1.f);
    return lo;
}
 
vector<ll> solve(vector<ll> v) {
    deque<pair<ll,ll>> dq;
    MOO(i, 1, n) {
        pair<ll,ll> curve = mp(i, v[i]);
        while(1) {
            if(dq.empty()) break;
            else if(intersect(dq[sz(dq)-1], curve) < 0) dq.pop_back();
            else {
                if(sz(dq) >= 2) {
                    if(intersect(dq[sz(dq)-2], curve) < intersect(dq[sz(dq)-2], dq[sz(dq)-1])) {
                        dq.pop_back();
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
        dq.pb(curve);
    }
    vector<ll> ans;
    M00(i, n-1) {
        while(dq[0].f <= i) dq.pop_front();
        while(sz(dq) >= 2 && eval(i, dq[1]) > eval(i, dq[0])) dq.pop_front();
        ans.pb(max(0LL,evalLong(i, dq[0])-v[i]));
    }
    ans.pb(-1);
    return ans;
}
 
int main() { FAST
    cin >> n;
    vector<ll> arr(n);
    M00(i, n) cin >> arr[i];
    vector<ll> res1 = solve(arr);
    reverse(all(arr));
    vector<ll> res2 = solve(arr);
    reverse(all(res2));
    M00(i, n) {
        cout << max(res1[i], res2[i]) << "\n";
    }
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 1556 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 2420 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 2936 KB Output is correct
2 Correct 20 ms 2944 KB Output is correct
3 Correct 39 ms 2936 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 4464 KB Output is correct
2 Correct 162 ms 5468 KB Output is correct
3 Correct 54 ms 4976 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 9580 KB Output is correct
2 Correct 371 ms 11672 KB Output is correct
3 Correct 112 ms 10860 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 15396 KB Output is correct
2 Correct 592 ms 15468 KB Output is correct
3 Correct 166 ms 15392 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 20120 KB Output is correct
2 Correct 821 ms 20288 KB Output is correct
3 Correct 253 ms 20120 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 20116 KB Output is correct
2 Correct 822 ms 24984 KB Output is correct
3 Correct 252 ms 22936 KB Output is correct