QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241797 | #7651. 傅里叶与交通规划 | hos_lyric# | 25 | 116ms | 85056kb | C++14 | 4.4kb | 2023-11-06 17:37:48 | 2024-07-04 02:22:57 |
Judging History
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<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]);
}
}
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: 60ms
memory: 15176kb
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: 9924kb
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: 10048kb
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: 10216kb
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: 10008kb
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: 3ms
memory: 43040kb
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: 0ms
memory: 43036kb
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: 6ms
memory: 42756kb
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: 5ms
memory: 43016kb
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: 0ms
memory: 42848kb
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: 116ms
memory: 85056kb
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: 11ms
memory: 68428kb
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: 3ms
memory: 55432kb
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: 3ms
memory: 38760kb
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: 100ms
memory: 80020kb
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: 42740kb
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: 42860kb
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: 26304kb
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: 0
Time Limit Exceeded
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:
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: 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%