QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226459 | #7329. Independent Events | PPP# | AC ✓ | 1333ms | 179240kb | C++17 | 2.5kb | 2023-10-25 23:18:13 | 2023-10-25 23:18:13 |
Judging History
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
int n, m;
const int maxN = 1e5 + 10;
ld p[maxN];
const int BUBEN = 40;
ld dp[2 * 134'000][BUBEN];
ld lazy[4 * maxN];
void merge(int v) {
for (int k = 0; k < BUBEN; k++) {
dp[v][k] = dp[2 * v][k] + dp[2 * v + 1][k];
}
}
void build(int v, int tl, int tr) {
lazy[v] = 0;
if (tl == tr) {
dp[v][0] = 1;
for (int z = 1; z < BUBEN; z++) {
dp[v][z] = dp[v][z - 1] * p[tl];
}
return;
}
// cout << " TUT " << v << " " << tl << " " << tr << endl;
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
merge(v);
}
ld ans = 0;
void apply(int v, ld k) {
ld x = 1;
lazy[v] += k;
ld f = expl(k);
for (int z = 0; z < BUBEN; z++) {
dp[v][z] *= x;
x *= f;
}
}
void push(int v, int tl, int tr) {
if (tl != tr) {
apply(2 * v, lazy[v]);
apply(2 * v + 1, lazy[v]);
}
lazy[v] = 0;
}
void go(int v, int tl, int tr, int l, int r) {
if (tr < l || tl > r) return;
if (l <= tl && tr <= r) {
for (int k = 1; k < BUBEN; k++) ans += dp[v][k] / k;
return;
}
push(v, tl, tr);
int tm = (tl + tr) / 2;
go(2 * v, tl, tm, l, r);
go(2 * v + 1, tm + 1, tr, l, r);
}
void upd(int v, int tl, int tr, int l, int r, ld k) {
if (tr < l || tl > r) return;
if (l <= tl && tr <= r) {
apply(v, k);
return;
}
push(v, tl, tr);
int tm = (tl + tr) / 2;
upd(2 * v, tl, tm, l, r, k);
upd(2 * v + 1, tm + 1, tr, l, r, k);
merge(v);
}
void solve() {
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
build(1, 1, n);
// cout << m << " ??? " << endl;
while (m--) {
int tp, l, r;
cin >> tp >> l >> r;
if (tp == 0) {
ans = 0;
go(1, 1, n, l, r);
cout << fixed << setprecision(25) << -ans << '\n';
}
else {
ld k;
cin >> k;
k = logl(k);
upd(1, 1, n, l, r, k);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
while (cin >> n >> m) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6044kb
input:
6 5 0.01000 0.09871 0.00005 0.00999 0.01234 0.02345 0 1 6 1 3 4 10.00000 0 1 6 1 1 2 0.05000 0 1 6
output:
-0.1602148772784847464864489 -0.2558741768948075731668779 -0.1473434773207209407333562
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 396ms
memory: 10180kb
input:
54 36 0.00014 0.00020 0.00054 0.00084 0.00088 0.00095 0.00031 0.00077 0.00054 0.00050 0.00024 0.00057 0.00066 0.00029 0.00084 0.00031 0.00024 0.00091 0.00063 0.00069 0.00024 0.00041 0.00090 0.00057 0.00071 0.00031 0.00047 0.00016 0.00063 0.00074 0.00040 0.00077 0.00058 0.00049 0.00013 0.00076 0.0007...
output:
-0.0009404420770566674692020 -0.1728569398412814199262081 -0.6472436841097425295208159 -0.0014473204722121014415070 -0.0929556419054982145409112 -0.9307832806009783100601590 -0.0641023931876947552504381 -0.0916640428180354913486510 -0.0477426923905568801302516 -0.0008501809013847735932844 -0.0318578...
result:
ok 49679 numbers
Test #3:
score: 0
Accepted
time: 200ms
memory: 7992kb
input:
13 5 0.00046 0.00033 0.00056 0.00093 0.00039 0.00094 0.00096 0.00085 0.00059 0.00083 0.00032 0.00075 0.00036 1 4 6 46.93710 0 3 11 0 5 8 1 4 13 2.21652 1 4 8 0.13103 4 14 0.00070 0.00028 0.00042 0.00079 0 1 1 0 4 4 0 3 3 1 2 2 100.00000 0 1 4 1 2 3 1.93082 1 3 4 100.00000 0 1 4 1 2 4 1.03435 0 2 4 0...
output:
-0.1123433435364657859476369 -0.0654097209605883984887714 -0.0007002451143933919669163 -0.0007903122144437701174552 -0.0004200882247037818547860 -0.0303101200752389201863765 -0.2231466796782917599612124 -0.2303983592301649602001549 -0.2310986043445583522045524 -0.0611907587584701614751275 -0.0344288...
result:
ok 49929 numbers
Test #4:
score: 0
Accepted
time: 676ms
memory: 16656kb
input:
625 1069 0.00107 0.00141 0.00178 0.00124 0.00104 0.00133 0.00188 0.00168 0.00108 0.00183 0.00199 0.00171 0.00122 0.00170 0.00133 0.00188 0.00128 0.00186 0.00165 0.00190 0.00117 0.00137 0.00129 0.00152 0.00136 0.00137 0.00135 0.00137 0.00134 0.00160 0.00159 0.00134 0.00124 0.00191 0.00193 0.00122 0.0...
output:
-5.2538348318205015394580237 -1.2009133348513624465342398 -4.8337652273409551662713968 -6.5182468011552673219956289 -4.7530413289572586710285407 -6.7893147690646935329267242 -1.0155258634981038406075102 -0.9262833802287792246688003 -6.0346911798305159909880380 -2.9882017760564989754690918 -7.7266646...
result:
ok 50073 numbers
Test #5:
score: 0
Accepted
time: 408ms
memory: 7996kb
input:
17 103 0.05363 0.09209 0.03209 0.01593 0.06746 0.07370 0.00889 0.02883 0.02923 0.01899 0.07308 0.09632 0.06342 0.02905 0.06267 0.00986 0.08607 0 9 16 0 1 13 0 7 16 0 11 15 0 6 16 1 2 12 0.29850 1 3 15 1.07403 1 6 7 1.70767 0 2 3 1 4 12 2.03798 0 5 16 1 3 17 0.51591 0 2 13 1 4 6 1.54691 0 4 5 0 7 14 ...
output:
-0.3956357585745123368772651 -0.6765166144983588179871552 -0.4338192591707600217218813 -0.3368884931198205463006440 -0.5103763818929152498281993 -0.0382150292054066769704523 -0.4873996440302715035634840 -0.2298732339995965688237388 -0.0441506796930221451431050 -0.1411694891914661922498230 -0.0404427...
result:
ok 50134 numbers
Test #6:
score: 0
Accepted
time: 671ms
memory: 18520kb
input:
1033 2717 0.00253 0.00437 0.00744 0.00171 0.00918 0.00727 0.00474 0.00776 0.00963 0.00289 0.00979 0.00582 0.00136 0.00251 0.00495 0.00481 0.00549 0.00589 0.00875 0.00696 0.00313 0.00590 0.00133 0.00298 0.00368 0.00440 0.00992 0.00505 0.00718 0.00321 0.00612 0.00612 0.00694 0.00824 0.00732 0.00506 0....
output:
-15.1673276581547048077677764 -2.8219622208358620836770453 -10.5025855104753414416204893 -3.2307199991626110243021774 -1.7688278661331275162403240 -0.1598713922435485490828287 -2.9759503929830361909809888 -1.3086334713552178825009611 -5.7889478526257791171465150 -5.9243602317034793577378571 -0.78854...
result:
ok 50323 numbers
Test #7:
score: 0
Accepted
time: 253ms
memory: 6060kb
input:
43 1 0.00466 0.00427 0.00409 0.00337 0.00412 0.00225 0.00235 0.00458 0.00300 0.00176 0.00223 0.00276 0.00410 0.00457 0.00129 0.00359 0.00432 0.00422 0.00311 0.00268 0.00270 0.00194 0.00135 0.00103 0.00175 0.00494 0.00460 0.00126 0.00438 0.00310 0.00246 0.00451 0.00122 0.00438 0.00336 0.00436 0.00210...
output:
-0.0034860692848318205526416 -0.0091771269828760729332699 -0.0116681656307783292339956 -0.1161046000974324003812417 -0.1554192478366957066629852 -0.2546958903701079083051976 -0.2050940192499858752422795 -0.3190884856286358551397900 -0.1662766620855303162563764 -0.0739413394855106198083833 -0.1653170...
result:
ok 50228 numbers
Test #8:
score: 0
Accepted
time: 377ms
memory: 10156kb
input:
169 109 0.00287 0.00227 0.00326 0.00125 0.00399 0.00434 0.00200 0.00297 0.00381 0.00372 0.00347 0.00247 0.00293 0.00319 0.00196 0.00178 0.00212 0.00286 0.00214 0.00275 0.00136 0.00209 0.00139 0.00218 0.00204 0.00414 0.00345 0.00140 0.00398 0.00241 0.00142 0.00392 0.00263 0.00182 0.00137 0.00253 0.00...
output:
-0.3169923256456425358560097 -0.5871188103731551701522720 -0.1335023356047056141391888 -2.3049809052736731443140200 -0.5681773585646809185856383 -1.2939642302660065162692171 -0.6038294828830682146490402 -0.4510934345777145953158577 -1.1257439985104464755076570 -0.6909961013525815099888157 -0.2553445...
result:
ok 50183 numbers
Test #9:
score: 0
Accepted
time: 380ms
memory: 8108kb
input:
47 31 0.00832 0.00849 0.00558 0.00815 0.00847 0.00582 0.00748 0.00705 0.00842 0.00508 0.00539 0.00808 0.00608 0.00996 0.00974 0.00602 0.00968 0.00672 0.00592 0.00766 0.00988 0.00696 0.00874 0.00811 0.00949 0.00595 0.00916 0.00909 0.00513 0.00683 0.00652 0.00802 0.00513 0.00879 0.00841 0.00694 0.0086...
output:
-0.0190524453876250269615240 -0.3138935435746991596431092 -0.0421054231792545679425980 -0.4253925999894273581296983 -0.3972846624326460341009633 -0.3244008926473640613287984 -0.2561890011458717810355519 -0.1680317934177899297671374 -0.2534489494878739390378367 -0.4497506563792313525240642 -0.4057818...
result:
ok 50055 numbers
Test #10:
score: 0
Accepted
time: 1327ms
memory: 176884kb
input:
100000 100000 0.07052 0.05432 0.02598 0.00422 0.07238 0.00101 0.07600 0.04658 0.00480 0.01504 0.06582 0.00826 0.05593 0.04165 0.09413 0.06963 0.07130 0.08360 0.09242 0.03682 0.09865 0.02278 0.05314 0.00652 0.09322 0.01022 0.00953 0.05682 0.08935 0.04186 0.07096 0.07263 0.02055 0.04193 0.02111 0.0034...
output:
-1961.8771934877960332332946791 -1029.1627950974558957097926282 -1378.6241932810043835377911137 -549.9810088259160159585015037 -28.0129061210540159683468620 -384.7329126004661057069977659 -655.1281534346620754050150026 -2797.0063164827225561381851549 -1983.3358145759111476058578205 -84.4147709888752...
result:
ok 49613 numbers
Test #11:
score: 0
Accepted
time: 1322ms
memory: 177112kb
input:
100000 100000 0.09844 0.07338 0.07328 0.05357 0.05732 0.03664 0.04328 0.05018 0.00685 0.05051 0.02626 0.07911 0.08921 0.04497 0.07470 0.04285 0.03429 0.08940 0.00033 0.01534 0.06782 0.08946 0.04441 0.03286 0.00432 0.03467 0.03984 0.09406 0.06030 0.07378 0.08303 0.05369 0.00232 0.06497 0.03548 0.0627...
output:
-1969.3625650654303321784865943 -2002.0875983836955367412002715 -1264.5815551229890736362193593 -2142.1914153583713817941003299 -921.9047251674169544677361898 -1278.3460420216346293820208757 -767.4910911044028389849103178 -1108.0204859049353676159199722 -16.3718702485114060429793881 -1277.6852877514...
result:
ok 50100 numbers
Test #12:
score: 0
Accepted
time: 1333ms
memory: 177144kb
input:
100000 100000 0.00156 0.00116 0.00173 0.00111 0.00137 0.00167 0.00158 0.00178 0.00109 0.00108 0.00178 0.00106 0.00113 0.00186 0.00165 0.00156 0.00124 0.00189 0.00161 0.00142 0.00189 0.00105 0.00133 0.00114 0.00165 0.00160 0.00120 0.00161 0.00119 0.00107 0.00116 0.00163 0.00189 0.00199 0.00166 0.0013...
output:
-24.0225816507063559632900729 -378.0220603786769341114748499 -1081.6285039772020714066158575 -748.3957491659882224066535628 -458.3332394434088584156405943 -33.1957219237883323290083659 -215.4893519475793154660525630 -869.0461318454755588192028881 -857.3365735314723095061850699 -528.26494588390889123...
result:
ok 50141 numbers
Test #13:
score: 0
Accepted
time: 1311ms
memory: 179240kb
input:
100000 100000 0.00228 0.00282 0.00213 0.00215 0.00212 0.00221 0.00232 0.00262 0.00251 0.00297 0.00207 0.00287 0.00254 0.00271 0.00267 0.00219 0.00211 0.00237 0.00207 0.00230 0.00295 0.00217 0.00212 0.00217 0.00277 0.00246 0.00209 0.00275 0.00286 0.00243 0.00262 0.00236 0.00213 0.00232 0.00234 0.0021...
output:
-15.3572059668877668363665134 -9.5616455129966637935604035 -11.2829585717465586004043532 -2099.1481757459285044653540808 -52.3888520048311980940869415 -0.7725576191874104339590498 -1081.8874008606377520314012486 -1237.0718049744786519728023677 -908.7232749540491920092755151 -1817.2532292876748241106...
result:
ok 50092 numbers
Test #14:
score: 0
Accepted
time: 1315ms
memory: 177200kb
input:
100000 100000 0.00823 0.00966 0.00140 0.00586 0.00383 0.00543 0.00448 0.00395 0.00566 0.00233 0.00126 0.00659 0.00220 0.00206 0.00429 0.00910 0.00290 0.00181 0.00822 0.00747 0.00186 0.00957 0.00831 0.00776 0.00877 0.00275 0.00116 0.00962 0.00821 0.00273 0.00827 0.00491 0.00971 0.00365 0.00533 0.0093...
output:
-185.4304201951696556005533267 -643.4124628880715443535187603 -1.1533185901096968593816314 -147.9297197469127888441731145 -25.8601005439117969265244712 -126.6044150258635483524694010 -25.2486742900884381206327856 -569.7642796219877816543686322 -341.7264929810826426803682665 -64.081348282236988124493...
result:
ok 50120 numbers
Test #15:
score: 0
Accepted
time: 1304ms
memory: 177128kb
input:
100000 100000 0.01388 0.02419 0.04321 0.04352 0.01515 0.04145 0.04269 0.03155 0.03102 0.03518 0.01190 0.04009 0.01123 0.04717 0.01548 0.02521 0.02603 0.04756 0.04362 0.01405 0.01642 0.02233 0.01474 0.03973 0.04126 0.03216 0.04967 0.04520 0.01937 0.01219 0.02545 0.02843 0.04214 0.01974 0.04543 0.0142...
output:
-2448.3882009498923812973458780 -1463.7670877982038776243811640 -219.3851595991071515429071681 -2603.7255145236169535660764041 -1640.0790669672212586105430887 -1376.0360850149020780497366445 -1403.7003730503408868157677603 -1244.2179989076024744232285002 -132.6647713547973621017739276 -51.2288310004...
result:
ok 49632 numbers
Test #16:
score: 0
Accepted
time: 1327ms
memory: 177260kb
input:
100000 100000 0.01843 0.04634 0.01012 0.02922 0.04612 0.01588 0.00456 0.02105 0.00209 0.00103 0.04947 0.03079 0.01097 0.04228 0.04366 0.00811 0.04394 0.00643 0.00587 0.00986 0.01118 0.04662 0.00956 0.04822 0.04171 0.01731 0.04787 0.03488 0.03921 0.02640 0.00369 0.04151 0.00450 0.03562 0.03141 0.0400...
output:
-609.0403471555675651294414763 -1222.1141706601558902800519490 -383.7800938860889120030073229 -656.5321333141829081014861913 -522.0227409958002265377707829 -181.4715125055508634227541265 -629.3735029751263201358568722 -379.8496242127656584153250208 -512.1255760776806049139331378 -300.047193422027336...
result:
ok 50162 numbers
Extra Test:
score: 0
Extra Test Passed