QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241793#7651. 傅里叶与交通规划hos_lyric#15 52ms8956kbC++143.4kb2023-11-06 17:27:422024-07-04 02:22:57

Judging History

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

  • [2024-07-04 02:22:57]
  • 评测
  • 测评结果:15
  • 用时:52ms
  • 内存:8956kb
  • [2023-11-06 17:27:42]
  • 提交

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 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<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 i, Int x, Int f) -> void {
      const Int w = (0 <= i && i < N) ? W[i] : 0;
      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]);
    check(i0, X0[q], f0);
    for (int i = 0; i <= N; ++i) {
      check(i - 1, P[i], fs[i]);
      check(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]);
    }
    
    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: 52ms
memory: 8956kb

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: 0ms
memory: 3780kb

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: 0ms
memory: 3876kb

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: 3784kb

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: 0ms
memory: 3852kb

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: 14ms
memory: 3996kb

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: 14ms
memory: 4136kb

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: 14ms
memory: 4092kb

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: 14ms
memory: 3836kb

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: 14ms
memory: 3960kb

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: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

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:


result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

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: 0
Time Limit Exceeded

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:


result:


Subtask #7:

score: 0
Time Limit Exceeded

Test #43:

score: 0
Time Limit Exceeded

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:


result:


Subtask #8:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #48:

score: 0
Time Limit Exceeded

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:


result:


Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #4:

0%