QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304642#8007. Egg Drop Challengeucup-team180#WA 1ms3760kbC++174.3kb2024-01-13 22:30:552024-01-13 22:30:56

Judging History

你现在查看的是最新测评结果

  • [2024-01-13 22:30:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3760kb
  • [2024-01-13 22:30:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const double INF = 1000000000000000000;
template <typename T1, typename T2, typename F>
struct abstract_li_chao_tree{
  int N;
  vector<T1> x;
  vector<F> ST;
  abstract_li_chao_tree(){
  }
  abstract_li_chao_tree(const vector<T1> &x2){
    x = x2;
    sort(x.begin(), x.end());
    int N2 = x.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    x.resize(N);
    for (int i = N2; i < N; i++){
      x[i] = x[N2 - 1];
    }
    ST = vector<F>(N * 2 - 1);
  }
  void line_add(F f, int i, int l, int r){
    T2 la = f.get(x[l]);
    T2 lb = ST[i].get(x[l]);
    T2 ra = f.get(x[r - 1]);
    T2 rb = ST[i].get(x[r - 1]);
    if (la >= lb && ra >= rb){
      return;
    } else if (la <= lb && ra <= rb){
      ST[i] = f;
    } else {
      int m = (l + r) / 2;
      T2 ma = f.get(x[m]);
      T2 mb = ST[i].get(x[m]);
      if (ma < mb){
        swap(f, ST[i]);
        swap(la, lb);
        swap(ra, rb);
      }
      if (la < lb){
        line_add(f, i * 2 + 1, l, m);
      }
      if (ra < rb){
        line_add(f, i * 2 + 2, m, r);
      }
    }
  }
  void line_add(F f){
    line_add(f, 0, 0, N);
  }
  void segment_add(int L, int R, F f, int i, int l, int r){
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      line_add(f, i, l, r);
    } else {
      int m = (l + r) / 2;
      segment_add(L, R, f, i * 2 + 1, l, m);
      segment_add(L, R, f, i * 2 + 2, m, r);
    }
  }
  void segment_add(T1 l, T1 r, F f){
    int pl = lower_bound(x.begin(), x.end(), l) - x.begin();
    int pr = lower_bound(x.begin(), x.end(), r) - x.begin();
    segment_add(pl, pr, f, 0, 0, N);
  }
  T2 get(T1 x2){
    int p = lower_bound(x.begin(), x.end(), x2) - x.begin();
    p += N - 1;
    T2 ans = INF;
    ans = min(ans, ST[p].get(x2));
    while (p > 0){
      p = (p - 1) / 2;
      ans = min(ans, ST[p].get(x2));
    }
    return ans;
  }
};
struct f1{
  double a;
  long long b;
  f1(): a(INF), b(0){
  }
  f1(double a, long long b): a(a), b(b){
  }
  double get(long long x){
    if (b - 2 * x >= 0){
      return a + sqrt(b - 2 * x);
    } else {
      return INF;
    }
  }
};
struct f2{
  double a;
  long long b;
  f2(): a(INF), b(INF){
  }
  f2(double a, long long b): a(a), b(b){
  }
  double get(long long x){
    if (x - 2 * b >= 0){
      return a - sqrt(x - 2 * b);
    } else {
      return INF * 2;
    }
  }
};
int main(){
  cout << fixed << setprecision(20);
  int n;
  cin >> n;
  vector<long long> h(n), v(n), u(n);
  for (int i = 0; i < n; i++){
    cin >> h[i] >> v[i] >> u[i];
  }
  vector<long long> V(n), U(n);
  for (int i = 0; i < n; i++){
    V[i] = v[i] * v[i] + 2 * h[i];
    U[i] = u[i] * u[i] + 2 * h[i];
  }
  vector<double> dp(n, INF);
  dp[n - 1] = 0;
  auto dc = [&](auto dc, int L, int R) -> void {
    if (R - L == 1){
      return;
    }
    int m = (L + R) / 2;
    dc(dc, m, R);
    vector<pair<long long, int>> P(R - L);
    for (int i = L; i < m; i++){
      P[i - L] = make_pair(U[i], i);
    }
    for (int i = m; i < R; i++){
      P[i - L] = make_pair(V[i], i);
    }
    sort(P.begin(), P.end());
    vector<double> A(R - m);
    for (int i = m; i < R; i++){
      A[i - m] = dp[i] - v[i];
    }
    vector<long long> x1(m - L);
    for (int i = 0; i < m - L; i++){
      x1[i] = h[i];
    }
    abstract_li_chao_tree<long long, double, f1> LCT1(x1);
    for (int i = 0; i < R - L; i++){
      int p = P[i].second;
      if (p >= m){
        LCT1.line_add(f1(A[p - m], V[p]));
      } else {
        dp[p] = min(dp[p], LCT1.get(h[p]));
      }
    }
    reverse(P.begin(), P.end());
    vector<double> B(m - L, INF);
    vector<long long> x2(m - L);
    for (int i = 0; i < m - L; i++){
      x2[i] = U[i];
    }
    abstract_li_chao_tree<long long, double, f2> LCT2(x2);
    for (int i = 0; i < R - L; i++){
      int p = P[i].second;
      if (p >= m){
        LCT2.line_add(f2(dp[p], h[p]));
      } else {
        B[p - L] = min(B[p - L], LCT2.get(U[p]));
      }
    }
    for (int i = L; i < m; i++){
      dp[i] = min(dp[i], B[i - L] + u[i]);
    }
    dc(dc, L, m);
  };
  dc(dc, 0, n);
  if (dp[0] >= INF / 2){
    cout << -1 << endl;
  } else {
    cout << dp[0] << endl;
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3760kb

input:

5
2 1 7
14 6 4
18 1 7
21 2 5
28 4 10

output:

6.00000000000000000000

result:

ok found '6.0000000', expected '6.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

2
1 1 4
10 5 1

output:

-1

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3760kb

input:

10
16 1 6
27 8 8
32 4 8
51 6 6
62 5 10
81 5 9
84 10 6
92 1 2
94 9 6
96 7 9

output:

-3.22693876101251042599

result:

wrong answer 1st numbers differ - expected: '12.8598310', found: '-3.2269388', error = '1.2509317'