QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601103 | #7329. Independent Events | Urd | AC ✓ | 1284ms | 229756kb | C++17 | 2.0kb | 2024-09-29 20:50:12 | 2024-09-29 20:50:12 |
Judging History
answer
#include <bits/stdc++.h>
#define ALL(v) begin(v), end(v)
using i64 = int64_t;
using f64 = long double;
const int kMaxN = 1E5 + 5, kExp = 15;
int n, m;
std::array<f64, kMaxN> p;
std::array<std::array<f64, kMaxN>, kExp> q;
class SegTree {
struct I {
int l, r;
f64 s, t;
};
std::array<I, kMaxN * 4> t;
std::array<f64, kMaxN> init;
void Up(int o) { t[o].s = t[o * 2].s + t[o * 2 + 1].s; }
void Upd(int o, f64 f) { t[o].t *= f, t[o].s *= f; }
void Down(int o) {
if (t[o].t != 1) Upd(o * 2, t[o].t), Upd(o * 2 + 1, t[o].t), t[o].t = 1;
}
public:
void Set(int x, f64 v) { init[x] = v; }
void Estab(int o, int l, int r) {
t[o].l = l, t[o].r = r, t[o].t = 1;
if (l == r) return void(t[o].s = init[l]);
int mid = (l + r) >> 1;
Estab(o * 2, l, mid), Estab(o * 2 + 1, mid + 1, r), Up(o);
}
void Mult(int o, int x, int y, f64 v) {
int l = t[o].l, r = t[o].r;
if (x <= l && r <= y) return Upd(o, v);
if (x > r || l > y) return;
Down(o), Mult(o * 2, x, y, v), Mult(o * 2 + 1, x, y, v), Up(o);
}
auto Sum(int o, int x, int y) {
int l = t[o].l, r = t[o].r;
if (x <= l && r <= y) return t[o].s;
if (x > r || l > y) return f64{0};
return Down(o), Sum(o * 2, x, y) + Sum(o * 2 + 1, x, y);
}
};
std::array<SegTree, kExp> t;
void Proc() {
for (int i = 1; i <= n; ++i) {
f64 f = 1;
std::cin >> p[i];
for (int j = 1; j < kExp; ++j) t[j].Set(i, f *= p[i]);
}
for (int i = 1; i < kExp; ++i) t[i].Estab(1, 1, n);
for (int op, l, r; m; --m) {
std::cin >> op >> l >> r;
if (op == 0) {
f64 ans = 0;
for (int e = 1; e < kExp; ++e) ans += t[e].Sum(1, l, r) / e;
std::cout << std::fixed << std::setprecision(15) << -ans << '\n';
} else {
f64 k, m = 1;
std::cin >> k;
for (int e = 1; e < kExp; ++e) t[e].Mult(1, l, r, m *= k);
}
}
}
auto main() -> int {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
while (std::cin >> n >> m) Proc();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 55052kb
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.160214877278485 -0.255874176894807 -0.147343477320721
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 220ms
memory: 59160kb
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.000940442077057 -0.172856939841281 -0.647243684109743 -0.001447320472212 -0.092955641905498 -0.930783280600978 -0.064102393187695 -0.091664042818035 -0.047742692390557 -0.000850180901385 -0.031857810983800 -0.237312223564791 -0.517538000548582 -0.653499425352686 -0.301089175013262 -0.062422318721...
result:
ok 49679 numbers
Test #3:
score: 0
Accepted
time: 110ms
memory: 57152kb
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.112343343536466 -0.065409720960588 -0.000700245114393 -0.000790312214444 -0.000420088224704 -0.030310120075239 -0.223146679678292 -0.230398359230165 -0.231098604344558 -0.061190758758470 -0.034428841303227 -0.192399078024270 -0.041068196006669 -0.088342494295396 -0.027706118655249 -0.001392560820...
result:
ok 49929 numbers
Test #4:
score: 0
Accepted
time: 419ms
memory: 69444kb
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.253834831820502 -1.200913334851362 -4.833765227340955 -6.518246801155267 -4.753041328957259 -6.789314769064694 -1.015525863498104 -0.926283380228779 -6.034691179830516 -2.988201776056499 -7.726664675934904 -1.080315155619918 -6.670126007056702 -2.185412176424858 -5.157565170832170 -8.414249963713...
result:
ok 50073 numbers
Test #5:
score: 0
Accepted
time: 234ms
memory: 59144kb
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.395635758574512 -0.676516614498359 -0.433819259170760 -0.336888493119821 -0.510376381892915 -0.038215029205407 -0.487399644030271 -0.229873233999597 -0.044150679693022 -0.141169489191466 -0.040442744920711 -0.056161897461915 -0.055121665890547 -0.176512379331239 -0.049472491529614 -0.010219826326...
result:
ok 50134 numbers
Test #6:
score: 0
Accepted
time: 407ms
memory: 67392kb
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.167327658154705 -2.821962220835862 -10.502585510475341 -3.230719999162611 -1.768827866133128 -0.159871392243549 -2.975950392983036 -1.308633471355218 -5.788947852625779 -5.924360231703479 -0.788549341490549 -5.900534211199786 -4.394460464419966 -5.878642061306236 -0.138563274535031 -4.8961708770...
result:
ok 50323 numbers
Test #7:
score: 0
Accepted
time: 144ms
memory: 55072kb
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.003486069284832 -0.009177126982876 -0.011668165630778 -0.116104600097432 -0.155419247836696 -0.254695890370108 -0.205094019249986 -0.319088485628636 -0.166276662085530 -0.073941339485511 -0.165317036344094 -0.024582041746790 -0.276475511187678 -0.072558443122629 -0.001744133232855 -0.035609999510...
result:
ok 50228 numbers
Test #8:
score: 0
Accepted
time: 215ms
memory: 59216kb
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.316992325645643 -0.587118810373155 -0.133502335604706 -2.304980905273673 -0.568177358564681 -1.293964230266007 -0.603829482883068 -0.451093434577715 -1.125743998510446 -0.690996101352582 -0.255344580605038 -0.924130008031568 -0.787400371298934 -0.108031746041346 -0.128276762797033 -0.131287121630...
result:
ok 50183 numbers
Test #9:
score: 0
Accepted
time: 214ms
memory: 57112kb
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.019052445387625 -0.313893543574699 -0.042105423179255 -0.425392599989427 -0.397284662432646 -0.324400892647364 -0.256189001145872 -0.168031793417790 -0.253448949487874 -0.449750656379231 -0.405781846382291 -0.136179615000673 -0.014801282574773 -0.228120182696162 -1.021975113286588 -0.024693422270...
result:
ok 50055 numbers
Test #10:
score: 0
Accepted
time: 1212ms
memory: 228168kb
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.877193487795866 -1029.162795097455896 -1378.624193281004309 -549.981008825915983 -28.012906121054016 -384.732912600466106 -655.128153434662075 -2797.006316482722500 -1983.335814575911137 -84.414770988875279 -375.776877683192105 -280.496555044462291 -489.519765225729347 -129.109300731536808 -22...
result:
ok 49613 numbers
Test #11:
score: 0
Accepted
time: 1201ms
memory: 224428kb
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.362565065430208 -2002.087598383695432 -1264.581555122988967 -2142.191415358371233 -921.904725167416926 -1278.346042021634609 -767.491091104402839 -1108.020485904935367 -16.371870248511406 -1277.685287751488737 -1354.669183618023875 -1697.427633785623991 -273.613936752037964 -460.84603726326318...
result:
ok 50100 numbers
Test #12:
score: 0
Accepted
time: 1241ms
memory: 229756kb
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.022581650706356 -378.022060378676934 -1081.628503977202012 -748.395749165988194 -458.333239443408858 -33.195721923788332 -215.489351947579315 -869.046131845475558 -857.336573531472308 -528.264945883908891 -82.317316524439469 -635.337143042145911 -528.593031573697899 -63.117246443613273 -130.4530...
result:
ok 50141 numbers
Test #13:
score: 0
Accepted
time: 1284ms
memory: 221656kb
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.357205966887767 -9.561645512996664 -11.282958571746559 -2099.148175745928386 -52.388852004831198 -0.772557619187410 -1081.887400860637704 -1237.071804974478604 -908.723274954049192 -1817.253229287674815 -1502.215328379160228 -518.655706846404500 -338.098220720479206 -153.194644583174139 -206.639...
result:
ok 50092 numbers
Test #14:
score: 0
Accepted
time: 1198ms
memory: 226164kb
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.430420195169656 -643.412462888071539 -1.153318590109697 -147.929719746912789 -25.860100543911797 -126.604415025863548 -25.248674290088438 -569.764279621987755 -341.726492981082643 -64.081348282236988 -23.953878478447870 -161.155423412959950 -561.050205237398736 -584.592798668911186 -57.13009725...
result:
ok 50120 numbers
Test #15:
score: 0
Accepted
time: 1199ms
memory: 227956kb
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.388200949892382 -1463.767087798203878 -219.385159599107152 -2603.725514523616954 -1640.079066967221259 -1376.036085014902078 -1403.700373050340887 -1244.217998907602475 -132.664771354797362 -51.228831000440995 -132.935242505912213 -1329.238435395070205 -1119.034630996487881 -0.849742950255133 ...
result:
ok 49632 numbers
Test #16:
score: 0
Accepted
time: 1175ms
memory: 227972kb
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.040347155567565 -1222.114170660155890 -383.780093886088912 -656.532133314182908 -522.022740995800227 -181.471512505550863 -629.373502975126306 -379.849624212765659 -512.125576077680595 -300.047193422027336 -57.720869512297716 -9.263595573921971 -274.056441623741264 -365.724232395259454 -518.786...
result:
ok 50162 numbers
Extra Test:
score: 0
Extra Test Passed