QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226459#7329. Independent EventsPPP#AC ✓1333ms179240kbC++172.5kb2023-10-25 23:18:132023-10-25 23:18:13

Judging History

This is the latest submission verdict.

  • [2023-10-25 23:18:13]
  • Judged
  • Verdict: AC
  • Time: 1333ms
  • Memory: 179240kb
  • [2023-10-25 23:18:13]
  • Submitted

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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