QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241815#7651. 傅里叶与交通规划hos_lyric#40 381ms96272kbC++146.2kb2023-11-06 17:55:042024-07-04 02:22:57

Judging History

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

  • [2024-07-04 02:22:57]
  • 评测
  • 测评结果:40
  • 用时:381ms
  • 内存:96272kb
  • [2023-11-06 17:55:04]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


using Double = double;
constexpr Double INF = 1e+100;

int N, Q;
Int V;
vector<Int> P;
vector<Int> W;
vector<Int> X0, Y0, X1, Y1;

int indexOf(Int x) {
  return (upper_bound(P.begin(), P.end(), x) - P.begin()) - 1;
}

namespace rmq {
constexpr int E = 18;
Int mn[E][1 << E], mx[E][1 << E];
void init() {
  mn[0][0] = mx[0][0] = 0;
  mn[0][N + 1] = mx[0][N + 1] = 0;
  for (int i = 0; i < N; ++i) {
    mn[0][i + 1] = mx[0][i + 1] = W[i];
  }
  for (int e = 0; e < E - 1; ++e) {
    for (int i = 0; i + (1 << (e + 1)) <= N + 2; ++i) {
      mn[e + 1][i] = min(mn[e][i], mn[e][i + (1 << e)]);
      mx[e + 1][i] = max(mx[e][i], mx[e][i + (1 << e)]);
    }
  }
}
pair<Int, Int> get(int iL, int iR) {
  if (iL > iR) swap(iL, iR);
  assert(-1 <= iL); assert(iL <= iR); assert(iR <= N);
  iL += 1;
  iR += 2;
  const int e = 31 - __builtin_clz(iR - iL);
  return make_pair(
    min(mn[e][iL], mn[e][iR - (1 << e)]),
    max(mx[e][iL], mx[e][iR - (1 << e)])
  );
}
}  // rmq

namespace brute {
vector<Int> fs;
Int calc(Int x) {
  const int i = indexOf(x);
  if (i < 0) return 0;
  if (i >= N) return fs[N];
  return fs[i] + W[i] * (x - P[i]);
}
vector<Double> run() {
cerr<<"[brute::run]"<<endl;
  fs.assign(N + 1, 0);
  for (int i = 0; i < N; ++i) {
    fs[i + 1] = fs[i] + W[i] * (P[i + 1] - P[i]);
  }
  vector<int> lefSmall(N), rigSmall(N);
  vector<int> lefLarge(N), rigLarge(N);
  {
    vector<pair<Int, int>> wis(N);
    for (int i = 0; i < N; ++i) wis[i] = make_pair(W[i], i);
    sort(wis.begin(), wis.end());
    {
      set<int> is{-1, N};
      for (int jL = 0, jR = 0; jL < N; jL = jR) {
        for (; jR < N && wis[jL].first == wis[jR].first; ++jR) {}
        for (int j = jL; j < jR; ++j) {
          const int i = wis[j].second;
          auto it = is.lower_bound(i);
          rigSmall[i] = *it;
          lefSmall[i] = *--it;
        }
        for (int j = jL; j < jR; ++j) {
          const int i = wis[j].second;
          is.insert(i);
        }
      }
    }
    reverse(wis.begin(), wis.end());
    {
      set<int> is{-1, N};
      for (int jL = 0, jR = 0; jL < N; jL = jR) {
        for (; jR < N && wis[jL].first == wis[jR].first; ++jR) {}
        for (int j = jL; j < jR; ++j) {
          const int i = wis[j].second;
          auto it = is.lower_bound(i);
          rigLarge[i] = *it;
          lefLarge[i] = *--it;
        }
        for (int j = jL; j < jR; ++j) {
          const int i = wis[j].second;
          is.insert(i);
        }
      }
    }
  }
// cerr<<"W = "<<W<<endl;
// cerr<<"  lefSmall = "<<lefSmall<<", rigSmall = "<<rigSmall<<endl;
// cerr<<"  lefLarge = "<<lefLarge<<", rigLarge = "<<rigLarge<<endl;
  vector<Double> ans(Q, INF);
  for (int q = 0; q < Q; ++q) {
    const Int f0 = calc(X0[q]);
    const Int f1 = calc(X1[q]);
    auto check = [&](Int w, Int x, Int f) -> void {
      Int dx = 0, dy = 0;
      dx += abs(x - X0[q]);
      dx += abs(x - X1[q]);
      dy += (X0[q] <= x) ? (f - f0) : (f0 - f);
      dy += (X1[q] <= x) ? (f - f1) : (f1 - f);
      /*
        yoko: (dx/V) sec
        tate: katteni (dy/V)
      */
      Double cost = 0.0;
      cost += (Double)dx / V;
      if (V * (Y1[q] - Y0[q]) >= dy) {
        cost += ((Y1[q] - Y0[q]) - (Double)dy / V) / (w + V);
      } else {
        cost += ((Y1[q] - Y0[q]) - (Double)dy / V) / (w - V);
      }
// cerr<<"check i="<<i<<" x="<<x<<" f="<<f<<": w="<<w<<", dx="<<dx<<", dy="<<dy<<", cost="<<cost<<endl;
      chmin(ans[q], cost);
    };
    const int i0 = indexOf(X0[q]);
    const int i1 = indexOf(X1[q]);
    const auto inside = rmq::get(i0, i1);
    check(inside.first, X0[q], f0);
    check(inside.second, X0[q], f0);
    /*
    for (int i = min(i0, i1); i >= 0; --i) {
      check((i == 0) ? 0 : W[i - 1], P[i], fs[i]);
    }
    for (int i = max(i0, i1) + 1; i <= N; ++i) {
      check((i == N) ? 0 : W[i], P[i], fs[i]);
    }
    */
    check(0, P[0], fs[0]);
    check(0, P[N], fs[N]);
    for (int i = min(i0, i1) - 1; i >= 0; i = lefSmall[i]) check(W[i], P[i + 1], fs[i + 1]);
    for (int i = min(i0, i1) - 1; i >= 0; i = lefLarge[i]) check(W[i], P[i + 1], fs[i + 1]);
    for (int i = max(i0, i1) + 1; i < N; i = rigSmall[i]) check(W[i], P[i], fs[i]);;
    for (int i = max(i0, i1) + 1; i < N; i = rigLarge[i]) check(W[i], P[i], fs[i]);;
  }
  return ans;
}
}  // brute


int main() {
  for (; ~scanf("%d%d%lld", &N, &Q, &V); ) {
    P.resize(N + 1);
    for (int i = 0; i <= N; ++i) {
      scanf("%lld", &P[i]);
    }
    W.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &W[i]);
    }
    X0.resize(Q);
    Y0.resize(Q);
    X1.resize(Q);
    Y1.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%lld%lld%lld%lld", &X0[q], &Y0[q], &X1[q], &Y1[q]);
    }
    
    rmq::init();
    
    const auto ans = brute::run();
    for (int q = 0; q < Q; ++q) {
      printf("%.8f\n", ans[q]);
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 53ms
memory: 15140kb

input:

0 149997 245221
260130

-353413 28107 189392 258734
122083 -105519 88981 -462313
62982 -221175 258110 442570
177977 -216904 -444299 246103
134500 179401 -402939 -459279
98037 -470438 -69318 43668
-204852 443991 -303144 -468157
-19237 -321861 40988 -450597
298668 -155343 -121990 491091
-446262 2335 -...

output:

3.15402025
1.58997802
3.50244473
4.42573434
4.79615938
2.77896673
4.12052801
0.77057430
4.35155227
0.78707370
2.41183259
3.24564780
4.03301512
2.32130609
1.24432655
4.13647281
2.06239270
2.43803345
2.29035441
2.68600976
3.05624314
3.45513639
3.94013155
2.41386749
4.75957198
3.09785867
0.37262714
0.3...

result:

ok 149997 numbers

Test #2:

score: 0
Accepted
time: 2ms
memory: 9928kb

input:

0 100 180744
464809

345260 -467272 -358539 328967
-47960 301643 54141 -6592
-43596 319458 -354462 -459419
-92196 310800 -85882 335949
153982 440647 336749 -116156
101998 -66169 149181 43052
-149130 -353 -398781 416947
-291725 221463 -136712 391161
105694 -5114 87525 234469
21942 -235999 209836 6442...

output:

8.29924092
2.27026070
6.02920706
0.17407493
4.09180941
0.86533440
3.69003120
1.79652437
1.42606117
2.70171071
2.86964436
4.16984243
3.87484508
4.18178750
4.62944828
3.62348404
3.76117050
2.17181207
3.82678263
1.22877661
4.10372129
2.52296065
2.96553689
4.42727283
3.63646373
2.52484177
5.38372505
6.7...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 9928kb

input:

0 96 112916
108050

-365188 332547 492134 -36526
-104666 473952 170125 173190
-234758 166079 187562 394112
-60172 -420595 -214538 460150
10825 55480 -120065 416458
351912 -140831 -73406 308683
-217445 -459449 51277 -72378
-176912 150232 144434 162328
-50628 -400429 -319790 -371228
327358 480500 3347...

output:

10.86112686
5.09717843
5.75961777
9.16708881
4.35605229
7.74763541
5.80779518
2.95300932
2.64234475
3.16722165
4.35376740
4.60013638
8.28630132
2.48132240
9.70007793
5.11102058
1.89044954
11.16963938
11.24308335
9.67789330
11.31193985
5.80470438
6.70501080
2.60430763
2.29521946
6.76313366
3.44829785...

result:

ok 96 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 10008kb

input:

0 98 22895
91189

-107939 77752 -276636 60647
386902 -56253 293764 -430313
231497 65839 344043 304956
-391967 441156 -160698 -32346
-64780 -107106 -221509 484371
-91709 224130 432009 480623
-489838 249592 -392494 -46576
-467214 -156595 -15098 -382701
-34447 443533 154513 317948
8797 -276399 434059 7...

output:

8.11539637
20.40611487
15.35981655
30.78274732
32.67988644
34.07778991
17.18768290
29.62314916
13.73858921
33.91945840
21.46490500
45.53858921
63.71260100
37.09071850
44.31640096
31.28464730
36.31661935
30.56217515
14.79423455
34.37287617
43.04564315
9.60397467
19.62590085
41.22747325
36.55562350
28...

result:

ok 98 numbers

Test #5:

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

input:

0 100 150548
10776

-338992 -479131 59003 172812
-231402 248648 269139 168600
-447255 262673 -479943 129977
266443 -494085 -99721 -439611
-328970 -239053 151827 -95253
144393 282865 221465 477090
265238 -268953 117580 107627
-320233 -224623 -394376 -382842
260411 288143 362003 -231710
-327178 195775...

output:

6.97410793
3.85650424
1.09854664
2.79404575
4.14882297
1.80206313
3.48219837
1.54344129
4.12788612
1.54292983
5.65552515
2.31542100
7.00387916
2.47851184
4.89175545
6.34711853
8.74582193
3.32192390
1.27725377
2.92590403
4.03245477
5.15509339
7.35045965
6.13361187
6.32190398
5.31443128
4.88996201
4.3...

result:

ok 100 numbers

Subtask #2:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 0ms
memory: 42848kb

input:

993 999 316326
-496532 -496093 -495620 -492330 -492168 -490309 -490221 -489706 -489674 -488540 -487445 -487205 -487063 -486731 -486636 -486525 -483675 -483348 -482170 -480225 -478996 -477851 -477476 -476245 -474426 -473611 -473054 -472532 -470524 -470223 -469519 -469003 -468790 -468648 -468210 -4680...

output:

0.99010577
1.57607674
2.57334584
2.67164505
2.52050013
2.59312045
1.12071575
3.34263720
0.35232732
3.94401275
2.03752604
1.98331717
2.35556910
1.09670729
3.20188003
0.71721534
2.19390824
1.56526473
2.40689070
1.58574632
0.91850959
2.55687581
0.83284001
0.76295398
1.37607412
2.91979169
1.08532667
3.4...

result:

ok 999 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 43092kb

input:

997 997 217603
-499799 -498333 -497404 -496957 -496655 -494826 -493913 -493091 -492990 -491277 -490056 -488767 -486657 -486543 -486528 -484217 -480512 -479591 -479562 -479559 -479159 -475469 -475297 -474181 -472973 -472661 -471212 -469422 -468661 -467326 -466468 -466262 -466067 -465341 -464845 -4643...

output:

1.10315413
2.04213627
2.80220658
2.96301554
1.25719017
0.59102322
2.00148114
1.38669390
0.49166153
2.50589746
2.63206611
1.11855330
1.72002029
3.93561193
1.87906938
2.36731687
5.85708015
0.15208288
1.18437640
5.54827737
2.12456558
3.09177448
3.97089190
1.95963096
2.62222884
3.66790539
3.31215838
1.7...

result:

ok 997 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 43128kb

input:

990 999 410563
-499636 -499493 -498362 -497772 -496607 -496251 -495502 -495291 -493565 -492200 -491876 -491569 -490203 -488666 -488637 -486272 -484197 -483586 -482754 -478432 -477269 -475235 -475067 -474547 -473480 -473411 -472262 -472236 -471888 -471339 -470160 -469159 -468072 -467881 -467211 -4661...

output:

1.45568369
0.85106182
1.59002304
1.63750780
1.47689464
0.87829694
0.52454148
0.70728837
1.00942848
1.21703711
0.55728022
0.96556329
0.76301772
1.66156757
1.47066171
1.42251255
2.14472562
0.86770401
2.48698503
0.58205739
1.12521280
0.84184861
0.99341925
0.89837199
0.79614209
1.49971601
1.10132344
0.5...

result:

ok 999 numbers

Test #9:

score: 0
Accepted
time: 4ms
memory: 42916kb

input:

999 991 278604
-499261 -498572 -498286 -495372 -493428 -492225 -490363 -487496 -487171 -485925 -484689 -484522 -483834 -482217 -481524 -481508 -479914 -478464 -477272 -476511 -475715 -475488 -475103 -473881 -472520 -471545 -468813 -467921 -467847 -467545 -465121 -464313 -462531 -462228 -461384 -4602...

output:

3.02300376
2.35961578
3.53346494
2.09374885
2.54324049
2.98178258
2.65666740
0.90686289
1.38028495
2.28961727
1.84235312
2.71083706
2.04573392
3.46622063
3.35640086
3.86226570
5.07207131
1.67539852
2.26548459
0.43374126
1.33803913
0.41368930
1.71830339
2.56779661
3.55257242
2.85706133
2.03814615
3.3...

result:

ok 991 numbers

Test #10:

score: 0
Accepted
time: 4ms
memory: 43112kb

input:

998 995 86259
-499764 -499107 -497424 -497246 -496766 -496696 -495855 -495537 -494905 -494468 -490023 -488774 -487401 -486388 -484946 -483405 -483153 -482740 -481457 -480043 -479973 -477456 -477212 -477029 -476323 -473012 -472991 -472761 -472734 -472112 -471906 -471690 -471578 -469858 -469637 -46872...

output:

5.51117669
5.94012013
12.87262087
4.94578325
2.31966038
10.89187986
12.02043319
7.68111978
3.24887869
10.40333746
12.58159340
9.71068730
2.15219750
6.12110270
10.75168657
7.34640668
8.21922217
8.60182083
8.64925664
12.41368190
4.77069304
8.28747830
2.55960575
9.92515972
9.05260941
13.00865596
7.4206...

result:

ok 995 numbers

Subtask #3:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 229ms
memory: 95596kb

input:

149928 149904 81074
-499992 -499987 -499981 -499968 -499965 -499961 -499949 -499941 -499940 -499933 -499925 -499923 -499911 -499899 -499893 -499892 -499877 -499868 -499865 -499858 -499852 -499849 -499845 -499838 -499837 -499836 -499826 -499822 -499819 -499815 -499803 -499801 -499797 -499785 -499783 ...

output:

16.85484255
14.99717971
15.81377823
16.64635760
13.26417734
14.49516610
13.76456979
14.23752335
12.53687517
15.46044490
13.33098133
14.53125681
13.98715794
16.95971100
14.12009115
12.95943964
15.13091021
14.89997779
12.70265067
14.60811429
14.16696392
14.73608946
16.36595002
12.87520397
17.25445860
...

result:

ok 149904 numbers

Test #12:

score: 0
Accepted
time: 27ms
memory: 72260kb

input:

49934 90 22588
-499984 -499964 -499955 -499950 -499937 -499923 -499867 -499863 -499860 -499854 -499851 -499795 -499784 -499737 -499731 -499729 -499709 -499703 -499701 -499678 -499676 -499673 -499655 -499590 -499587 -499559 -499536 -499488 -499465 -499453 -499447 -499371 -499351 -499338 -499335 -4993...

output:

51.65172809
45.77828498
58.73637855
48.50674098
54.04567150
48.75563971
64.87588321
45.71893800
44.44781459
46.88230269
45.80852294
50.52098917
60.25123223
61.66928243
47.14567845
45.07119035
47.35739949
50.28456999
52.47920363
44.55603145
44.46638681
56.41170064
55.76019756
61.66244657
53.09910932
...

result:

ok 90 numbers

Test #13:

score: 0
Accepted
time: 6ms
memory: 55796kb

input:

4964 92 138367
-499797 -499471 -499299 -499268 -498616 -498541 -498312 -497850 -497119 -496699 -496505 -496336 -496195 -495977 -495739 -495693 -495376 -495255 -495240 -495084 -495061 -494981 -494958 -494841 -494830 -494713 -494615 -494334 -493926 -493804 -493711 -493618 -493583 -493537 -493414 -4930...

output:

8.51911185
7.69964487
8.83104228
7.41149921
10.00588952
8.66494355
8.49453501
8.84660241
7.54651532
8.64001571
8.63602037
7.87768652
8.89298285
7.53201640
8.30546576
7.34587787
8.35959869
7.44396159
8.57703571
8.86774081
7.59168521
7.83628922
9.04076158
8.88027315
8.37110075
8.33400362
9.79369220
8....

result:

ok 92 numbers

Test #14:

score: 0
Accepted
time: 0ms
memory: 38664kb

input:

473 91 280891
-499695 -491193 -490954 -488064 -487152 -486813 -486653 -483884 -483780 -483560 -482582 -478635 -477514 -469765 -468404 -463396 -459567 -459150 -458362 -457468 -456519 -455992 -453760 -447451 -445214 -443060 -439883 -438546 -431873 -422100 -416682 -415799 -408108 -403186 -402593 -40244...

output:

4.99715489
4.10254530
4.67681200
4.69592650
3.93638151
3.56008568
3.56435944
4.79774508
4.30378529
4.81691807
3.71844565
4.30936295
3.72882050
4.60790391
3.98717030
3.95525638
3.61683372
3.84615420
4.48827995
4.90758055
4.40088936
3.95280530
5.19179450
4.47521039
5.14411633
3.58170075
4.18386990
4.5...

result:

ok 91 numbers

Test #15:

score: 0
Accepted
time: 122ms
memory: 86584kb

input:

99944 149372 113369
-499995 -499983 -499979 -499978 -499964 -499950 -499946 -499929 -499923 -499921 -499914 -499893 -499880 -499863 -499831 -499814 -499805 -499796 -499788 -499787 -499781 -499779 -499748 -499747 -499745 -499734 -499700 -499698 -499695 -499688 -499665 -499660 -499640 -499630 -499624 ...

output:

10.66995160
10.22523371
9.40459231
13.11014646
9.45820407
10.67284482
11.12234799
12.13606873
8.94030448
8.86788140
11.12247826
10.21857010
8.86418539
11.12636392
10.23832479
9.26073740
9.33277240
11.39729291
9.52413067
10.60661390
10.61586691
9.63188106
9.46534450
9.02182624
9.19026368
10.92778336
...

result:

ok 149372 numbers

Test #16:

score: 0
Accepted
time: 0ms
memory: 42872kb

input:

854 92 154270
-498878 -498558 -498030 -496154 -495734 -495439 -494928 -492469 -489873 -489750 -489153 -488956 -486460 -485436 -485019 -484168 -484159 -483513 -482927 -482269 -480851 -480501 -477526 -476301 -475337 -474926 -474617 -473968 -471575 -471389 -471126 -470407 -469246 -468844 -468789 -46854...

output:

7.00593540
6.62119124
7.10736216
7.12663209
6.56044703
6.69440919
6.77164931
9.30981800
8.03545417
7.37545167
6.74030618
7.16472267
7.17813797
6.70805669
7.89829824
6.49230272
6.49141834
8.44668419
6.60850166
7.02005249
7.32439933
7.15388170
7.08649212
9.42871893
7.02973256
8.00548413
7.62910608
6.4...

result:

ok 92 numbers

Test #17:

score: 0
Accepted
time: 0ms
memory: 42928kb

input:

811 97 204269
-499023 -498121 -496051 -494631 -493384 -492924 -492159 -491576 -489519 -488007 -487026 -485511 -484439 -483918 -480089 -479139 -478859 -475982 -475457 -472489 -472374 -471297 -468837 -468199 -466579 -464763 -463487 -462936 -461462 -459463 -457411 -454221 -453778 -453325 -448427 -44791...

output:

6.36939258
6.32327795
5.32598885
6.97236746
6.49094947
6.88560163
5.01994406
5.14398458
4.93968032
4.89196379
5.52001753
6.89457673
5.25294522
5.22100834
5.00775807
6.29387685
7.15555256
6.90054462
6.44042716
5.61074397
5.29649715
4.92208731
5.11718370
5.24878249
4.89919411
6.52862803
5.26184076
5.8...

result:

ok 97 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 26336kb

input:

44 92 23756
-455424 -411003 -394907 -345645 -344017 -301113 -285315 -272511 -248317 -205733 -183557 -179295 -160321 -90555 -61719 -60568 -48097 -47091 -38706 -35645 -31598 -17875 -6000 27003 53825 80267 80971 87486 110173 117577 117796 144115 145782 190489 221315 284071 317664 361721 369142 388959 3...

output:

56.89069567
52.79929958
43.13868954
41.26747494
47.43074158
43.16260996
39.86469807
45.86146044
44.71918588
47.91251703
46.51411318
52.61481291
39.83875362
58.17682227
42.70630428
47.82534374
42.53282970
44.35679055
50.74612368
48.03853083
54.34567277
45.92895969
54.76564193
41.52419299
46.39687256
...

result:

ok 92 numbers

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #3:

100%
Accepted

Test #19:

score: 10
Accepted
time: 236ms
memory: 96272kb

input:

149911 149947 116886
-499997 -499992 -499991 -499971 -499963 -499944 -499929 -499919 -499901 -499896 -499889 -499885 -499874 -499872 -499869 -499865 -499857 -499851 -499846 -499839 -499830 -499829 -499828 -499820 -499817 -499810 -499809 -499789 -499777 -499773 -499771 -499770 -499769 -499764 -499763...

output:

5.03500346
6.80069196
7.42041176
4.77755811
5.91877121
5.48878282
7.20968551
5.54992327
8.26868187
5.11020441
4.92583633
7.66136092
6.11245027
5.51023350
4.98506057
7.31379886
5.97539693
6.03123554
7.36567464
5.62849002
5.98901329
6.44867930
7.73731343
5.45358583
5.77809454
5.42859546
6.00820366
4.8...

result:

ok 149947 numbers

Test #20:

score: 0
Accepted
time: 42ms
memory: 72464kb

input:

49998 976 4301
-499995 -499977 -499966 -499952 -499950 -499933 -499880 -499857 -499856 -499830 -499821 -499809 -499794 -499772 -499764 -499706 -499703 -499692 -499667 -499661 -499652 -499648 -499645 -499631 -499559 -499557 -499553 -499544 -499520 -499482 -499462 -499371 -499334 -499325 -499313 -4993...

output:

114.93071125
57.40564436
31.72331332
33.11000202
69.96094959
63.19789747
51.73331681
32.06285036
115.65947302
62.39296552
93.32672101
37.98001714
68.41415270
44.28881844
90.09518723
42.25324118
47.17661098
79.23302601
58.61688084
49.15395040
52.28056359
40.68062401
52.29897925
102.41320514
119.37032...

result:

ok 976 numbers

Test #21:

score: 0
Accepted
time: 0ms
memory: 42908kb

input:

975 953 93061
-492823 -492732 -492028 -491965 -491471 -491081 -490667 -490639 -487837 -487619 -486792 -486356 -484286 -484110 -481761 -481264 -480617 -480485 -478327 -477885 -476349 -476237 -476008 -474874 -474014 -471434 -470499 -468490 -467607 -467230 -467222 -467149 -464670 -463610 -462464 -46069...

output:

3.49617382
3.86421867
2.99902025
3.17260391
3.69646491
2.67678403
4.81260909
3.91196273
4.59904698
4.35061293
4.30572586
5.35192284
6.82154172
2.86055310
2.78892756
2.55896008
4.54221985
3.84520083
2.49452970
6.01004369
2.48954386
4.94696353
3.69292332
4.87916126
4.49365104
7.14540028
5.31145251
7.2...

result:

ok 953 numbers

Test #22:

score: 0
Accepted
time: 0ms
memory: 30524kb

input:

94 904 44506
-484085 -455725 -454829 -451090 -445346 -432295 -426196 -425404 -405212 -393305 -392640 -350172 -329071 -325454 -292817 -288714 -286102 -276925 -260864 -247808 -244808 -219022 -210685 -203440 -199935 -199520 -199078 -171835 -129706 -118160 -115764 -99952 -87065 -72779 -71852 -63658 -617...

output:

13.91746864
6.98179073
16.06942269
16.08955205
8.59256962
7.05600659
7.53928786
7.75463753
8.37204078
11.45068534
12.69791435
9.32246817
9.03623390
12.10048169
9.36762991
14.82475776
10.49914251
7.85546825
6.13752797
8.85698818
7.24938119
10.82177848
12.96893163
8.96971412
11.44495423
15.95460700
8....

result:

ok 904 numbers

Test #23:

score: -10
Time Limit Exceeded

input:

99912 149987 148904
-499993 -499992 -499988 -499982 -499980 -499978 -499963 -499959 -499948 -499923 -499922 -499910 -499909 -499901 -499898 -499886 -499874 -499862 -499861 -499853 -499841 -499838 -499820 -499816 -499815 -499813 -499803 -499794 -499787 -499775 -499733 -499732 -499724 -499723 -499721 ...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #27:

score: 0
Time Limit Exceeded

input:

149957 149927 72015
-499992 -499989 -499986 -499981 -499980 -499970 -499957 -499950 -499947 -499937 -499929 -499928 -499925 -499915 -499913 -499905 -499885 -499881 -499868 -499859 -499856 -499852 -499848 -499839 -499835 -499828 -499821 -499815 -499814 -499809 -499808 -499799 -499797 -499792 -499783 ...

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #34:

score: 15
Accepted
time: 359ms
memory: 95992kb

input:

149278 149093 342851
-499997 -499996 -499993 -499975 -499974 -499969 -499955 -499954 -499942 -499939 -499935 -499934 -499926 -499905 -499901 -499895 -499893 -499883 -499882 -499872 -499865 -499862 -499859 -499815 -499807 -499805 -499799 -499779 -499765 -499755 -499741 -499736 -499729 -499701 -499688...

output:

1.23446280
1.08260762
0.67585857
0.59273972
0.51481140
0.09565943
0.15518115
0.06583307
0.46282966
0.05887430
0.11873674
0.69494125
0.02925277
0.26799179
0.01014910
0.67951105
1.09445186
0.45012580
0.32870133
0.71116124
0.01043230
0.07701389
0.38537240
0.58054998
0.79641831
0.42444881
1.03460451
1.1...

result:

ok 149093 numbers

Test #35:

score: 0
Accepted
time: 46ms
memory: 72324kb

input:

49950 9663 218965
-499987 -499977 -499952 -499947 -499870 -499828 -499824 -499798 -499787 -499774 -499763 -499756 -499741 -499718 -499712 -499707 -499675 -499660 -499631 -499579 -499555 -499553 -499537 -499532 -499531 -499502 -499493 -499464 -499399 -499389 -499373 -499322 -499313 -499270 -499182 -4...

output:

0.75482748
1.10303987
1.37927977
0.14098450
1.98119733
0.03559078
0.17484048
0.11065824
1.80276529
1.59381671
1.00966073
0.74568952
0.57872315
1.47537978
1.45743565
0.28376634
0.95626209
1.45280941
0.50903692
0.28048300
0.25704121
0.23162779
1.84243489
0.71614840
0.71423671
1.43910238
0.17710547
1.8...

result:

ok 9663 numbers

Test #36:

score: 0
Accepted
time: 3ms
memory: 55548kb

input:

4995 932 493038
-499937 -499747 -499287 -499117 -499070 -498902 -498704 -498628 -498537 -497816 -497759 -497331 -496999 -496719 -496109 -495954 -495482 -495041 -494685 -494298 -494204 -493930 -493885 -493456 -493114 -493014 -492957 -492503 -492311 -492265 -491100 -491025 -490863 -490701 -490526 -490...

output:

0.53334985
0.25264396
0.78739186
0.01986276
0.07752463
0.07989210
0.17769833
0.47086217
0.70777652
0.79304351
0.41535042
0.37691245
0.13398433
0.73807630
0.35517617
0.23863921
0.35858065
0.65708886
0.27712402
0.04590901
0.12421497
0.40220083
0.17647402
0.49524977
0.25435949
0.38640143
0.87857545
0.4...

result:

ok 932 numbers

Test #37:

score: 0
Accepted
time: 0ms
memory: 38952kb

input:

367 910 93569
-494593 -492783 -491608 -491398 -486772 -485715 -485133 -482589 -475662 -474200 -469800 -465963 -464254 -463888 -456575 -454713 -454155 -450740 -441318 -437684 -435619 -435110 -429607 -423889 -421753 -418100 -411326 -409590 -407824 -406727 -404200 -402472 -402348 -401394 -398549 -39820...

output:

1.68848267
1.09031458
0.69093451
5.17195066
2.94588190
2.74507622
1.28291631
1.90122252
4.03623979
4.95994791
1.94069467
0.37519475
4.78841567
4.35708547
4.13314439
0.21093435
4.28748488
1.16533476
0.63113539
3.90222085
2.30144897
1.55889925
2.34269227
3.94854109
3.77019500
0.82579465
1.65361220
2.0...

result:

ok 910 numbers

Test #38:

score: 0
Accepted
time: 0ms
memory: 43052kb

input:

831 932 430975
-499988 -498573 -498078 -495703 -494248 -493478 -493238 -492018 -490139 -488536 -488434 -487719 -487380 -483132 -478519 -477733 -476732 -476067 -476045 -476041 -475764 -472850 -472352 -472057 -470523 -470088 -468459 -466265 -465601 -464365 -461999 -461043 -460607 -459586 -457526 -4555...

output:

0.78708433
0.21709640
0.03859383
0.56947805
0.15072472
0.29366493
0.26779319
0.04997299
0.46627858
0.23441290
0.18951119
0.51137746
0.04405861
0.17685706
0.46002508
0.26166328
0.50502088
0.75077089
0.27006315
0.05427941
0.73331489
0.74628879
0.39747949
0.85831755
0.73319910
0.23113509
0.13015485
0.6...

result:

ok 932 numbers

Test #39:

score: -15
Time Limit Exceeded

input:

149978 149588 305623
-500000 -499995 -499988 -499983 -499982 -499971 -499968 -499966 -499960 -499954 -499953 -499952 -499950 -499949 -499929 -499920 -499908 -499897 -499888 -499885 -499879 -499877 -499875 -499874 -499872 -499868 -499864 -499862 -499851 -499846 -499843 -499841 -499840 -499839 -499837...

output:


result:


Subtask #7:

score: 15
Accepted

Test #43:

score: 15
Accepted
time: 381ms
memory: 95220kb

input:

149990 149944 141363
-499995 -499994 -499993 -499990 -499956 -499950 -499947 -499924 -499921 -499916 -499914 -499888 -499876 -499870 -499869 -499863 -499855 -499848 -499846 -499837 -499836 -499833 -499832 -499815 -499813 -499799 -499787 -499775 -499770 -499769 -499767 -499766 -499762 -499757 -499753...

output:

2.85905793
1.31671388
3.12882822
6.23474730
5.07393036
3.69524523
3.29137143
5.50028330
1.28931668
2.42087222
0.73993127
0.91882973
3.61397963
2.30513854
3.73927801
0.59207535
0.71543114
3.68421070
2.11249528
0.58018545
2.96508347
6.57030367
5.38212914
3.22122912
1.86715448
3.97327458
4.86391909
1.6...

result:

ok 149944 numbers

Test #44:

score: 0
Accepted
time: 363ms
memory: 96216kb

input:

149927 149976 2798
-499981 -499980 -499974 -499971 -499969 -499967 -499954 -499953 -499952 -499948 -499938 -499928 -499918 -499902 -499898 -499886 -499885 -499883 -499878 -499871 -499864 -499855 -499834 -499828 -499827 -499816 -499809 -499803 -499802 -499799 -499793 -499779 -499773 -499772 -499770 -...

output:

129.43248145
199.05771919
256.64906038
143.67583791
130.50764864
150.64670117
47.24497350
341.27670856
141.63823093
49.89180222
59.97951939
226.39215807
280.72088534
99.30549997
88.43650437
181.40947568
215.73452990
146.70012003
268.90219862
99.51309253
53.22662204
396.70970922
145.23109217
28.95296...

result:

ok 149976 numbers

Test #45:

score: 0
Accepted
time: 4ms
memory: 42788kb

input:

633 990 375971
-499674 -499550 -493916 -492655 -491141 -489644 -489377 -489054 -487790 -482760 -482579 -478150 -477350 -477345 -476950 -473151 -472647 -472507 -470233 -469218 -468453 -463068 -461958 -460395 -459448 -459372 -459056 -458108 -457518 -453548 -451892 -451064 -449878 -442024 -440496 -4396...

output:

1.08125890
1.00901343
1.27362447
0.04727399
0.33492772
0.41424515
1.04843391
1.09811899
1.02390269
1.06327016
2.20638670
1.95163137
2.02071186
0.34178366
1.23057616
1.17575362
1.44583550
1.21238584
1.39991219
2.53769836
1.16202710
0.90438114
3.36690076
1.93801432
2.61811347
1.50422309
1.15043044
1.0...

result:

ok 990 numbers

Test #46:

score: 0
Accepted
time: 2ms
memory: 43100kb

input:

825 995 236205
-499213 -495358 -495254 -493281 -492771 -492500 -486576 -486304 -485361 -484884 -482973 -476757 -476452 -476447 -476435 -474868 -472626 -469274 -466803 -466605 -464583 -464518 -464263 -462979 -462145 -461978 -461385 -459652 -455894 -452903 -451440 -450394 -450046 -449912 -449264 -4482...

output:

3.93668159
3.06121884
1.51456475
2.21019166
2.48529278
1.05105185
0.81644468
3.18487734
0.28197195
4.79436230
2.94016112
3.90970952
1.39917141
3.90374358
3.67697751
1.39472172
2.13065869
1.35842284
4.86304620
2.00936766
1.73338669
4.16929773
4.30663003
2.32030575
3.14169780
4.30124107
4.09467442
2.0...

result:

ok 995 numbers

Test #47:

score: 0
Accepted
time: 0ms
memory: 38908kb

input:

336 994 323417
-497309 -497035 -496446 -487637 -487318 -486982 -481391 -475964 -472481 -470249 -467508 -461235 -460923 -453811 -453415 -453094 -452867 -446051 -445912 -438676 -434322 -424520 -414188 -412705 -411025 -410378 -408410 -400585 -394921 -394840 -385111 -384853 -382761 -380545 -379531 -3785...

output:

2.26507065
1.28574252
1.58407242
1.95837532
0.87623844
2.76732988
2.38406758
0.59294729
2.32050104
0.76651295
1.68038275
1.39341457
1.48485532
1.23970017
0.92757086
0.34552716
1.25579528
3.21426597
0.37486433
0.37323106
1.18183633
0.53298827
1.29737861
2.91976543
1.13607266
2.36060073
0.74340389
1.6...

result:

ok 994 numbers

Subtask #8:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #48:

score: 10
Accepted
time: 109ms
memory: 73644kb

input:

49982 49912 98988
-499997 -499929 -499912 -499874 -499844 -499825 -499814 -499742 -499709 -499646 -499643 -499626 -499602 -499579 -499554 -499512 -499509 -499507 -499483 -499479 -499381 -499365 -499223 -499204 -499192 -499179 -499147 -499144 -499120 -499046 -499020 -498997 -498994 -498955 -498954 -4...

output:

7.69917377
1.91858599
4.28787383
0.89898874
10.49792470
2.63230978
4.23177722
3.71182650
0.67897894
5.55553695
4.48577694
2.01655423
4.71993301
10.96916447
7.45411816
7.05923964
0.71036674
5.90735335
7.31839422
7.11330958
4.92787063
2.74194504
1.68808867
2.61038333
2.08359038
4.00841840
4.32135865
6...

result:

ok 49912 numbers

Test #49:

score: 0
Accepted
time: 7ms
memory: 55964kb

input:

4940 4981 341461
-499494 -499394 -499304 -499154 -499096 -499077 -499051 -499008 -498915 -498781 -498684 -498511 -498027 -497794 -497633 -497334 -497221 -497187 -497149 -496719 -496574 -496488 -496388 -496372 -496323 -496303 -496079 -495918 -495375 -495146 -495067 -494634 -493879 -493792 -493483 -49...

output:

1.77184364
0.36058898
2.44614347
1.55024200
0.32806439
1.32062188
0.96939835
1.73770107
1.70576631
0.60990705
1.39448387
1.61420709
0.30403138
2.98412306
1.81274257
1.38902786
1.71289464
1.68220309
1.79867055
1.26380193
1.75869105
1.21224067
0.45327626
0.73623741
2.25829144
3.62098244
1.88710432
2.4...

result:

ok 4981 numbers

Test #50:

score: 0
Accepted
time: 0ms
memory: 38812kb

input:

496 500 346404
-497896 -497005 -495935 -495154 -491603 -490440 -488905 -483779 -479887 -471916 -471799 -470461 -470001 -469509 -467992 -467787 -467648 -467143 -466216 -462395 -461599 -461191 -457726 -455930 -453547 -451800 -448684 -448507 -446794 -446523 -446347 -443912 -440802 -440688 -439740 -4368...

output:

1.74193291
0.83762729
0.66523321
0.75708754
1.94385136
2.93198241
2.22980337
0.55117205
1.58487654
1.71298797
1.04305600
0.97107194
1.26129066
1.18387228
2.26714297
0.73377808
1.96102499
1.59135286
0.16297014
0.53913395
1.05343833
0.35571402
1.00708595
3.25590571
1.67043308
1.97542564
1.26625765
0.9...

result:

ok 500 numbers

Test #51:

score: -10
Time Limit Exceeded

input:

49369 49955 356633
-499992 -499985 -499977 -499955 -499952 -499941 -499907 -499888 -499887 -499856 -499841 -499831 -499799 -499770 -499753 -499694 -499680 -499678 -499667 -499662 -499657 -499651 -499635 -499584 -499569 -499557 -499537 -499468 -499424 -499374 -499353 -499349 -499345 -499318 -499312 -...

output:


result:


Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #4:

0%