QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714846 | #7329. Independent Events | hos_lyric | AC ✓ | 177ms | 47224kb | C++14 | 7.5kb | 2024-11-06 08:37:51 | 2024-11-06 08:37:55 |
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")
// T: monoid representing information of an interval.
// T() should return the identity.
// T(S s) should represent a single element of the array.
// T::push(T &l, T &r) should push the lazy update.
// T::pull(const T &l, const T &r) should pull two intervals.
template <class T> struct SegmentTreeRange {
int logN, n;
vector<T> ts;
SegmentTreeRange() : logN(0), n(0) {}
explicit SegmentTreeRange(int n_) {
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
}
template <class S> explicit SegmentTreeRange(const vector<S> &ss) {
const int n_ = ss.size();
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
build();
}
T &at(int i) {
return ts[n + i];
}
void build() {
for (int u = n; --u; ) pull(u);
}
inline void push(int u) {
ts[u].push(ts[u << 1], ts[u << 1 | 1]);
}
inline void pull(int u) {
ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
}
// Applies T::f(args...) to [a, b).
template <class F, class... Args>
void ch(int a, int b, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return;
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) (ts[aa++].*f)(args...);
if (bb & 1) (ts[--bb].*f)(args...);
}
for (int h = 1; h <= logN; ++h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) pull(aa);
} else {
if ((aa << h) != a) pull(aa);
if ((bb << h) != b) pull(bb);
}
}
}
// Calculates the product for [a, b).
T get(int a, int b) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return T();
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
T prodL, prodR, t;
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) { t.pull(prodL, ts[aa++]); prodL = t; }
if (bb & 1) { t.pull(ts[--bb], prodR); prodR = t; }
}
t.pull(prodL, prodR);
return t;
}
// Calculates T::f(args...) of a monoid type for [a, b).
// op(-, -) should calculate the product.
// e() should return the identity.
template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
auto
#else
decltype((std::declval<T>().*F())())
#endif
get(int a, int b, Op op, E e, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return e();
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
auto prodL = e(), prodR = e();
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...));
if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR);
}
return op(prodL, prodR);
}
// Find min b s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from left to right.
// Returns n + 1 if there is no such b.
template <class F, class... Args>
int findRight(int a, F f, Args &&... args) {
assert(0 <= a); assert(a <= n);
if ((T().*f)(args...)) return a;
if (a == n) return n + 1;
a += n;
for (int h = logN; h; --h) push(a >> h);
for (; ; a >>= 1) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < n; ) {
push(a);
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - n + 1;
}
++a;
if (!(a & (a - 1))) return n + 1;
}
}
// Find max a s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from right to left.
// Returns -1 if there is no such a.
template <class F, class... Args>
int findLeft(int b, F f, Args &&... args) {
assert(0 <= b); assert(b <= n);
if ((T().*f)(args...)) return b;
if (b == 0) return -1;
b += n;
for (int h = logN; h; --h) push((b - 1) >> h);
for (; ; b >>= 1) if ((b & 1) || b == 2) {
if ((ts[b - 1].*f)(args...)) {
for (; b <= n; ) {
push(b - 1);
if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
}
return b - n - 1;
}
--b;
if (!(b & (b - 1))) return -1;
}
}
};
////////////////////////////////////////////////////////////////////////////////
constexpr int K = 20;
struct Node {
double sums[K];
double lz;
Node() : sums{}, lz(1.0) {}
Node(double p) : lz(1.0) {
sums[0] = 1.0;
for (int k = 1; k < K; ++k) sums[k] = sums[k - 1] * p;
}
void push(Node &l, Node &r) {
if (lz != 1.0) {
l.mul(lz);
r.mul(lz);
lz = 1.0;
}
}
void pull(const Node &l, const Node &r) {
for (int k = 0; k < K; ++k) sums[k] = l.sums[k] + r.sums[k];
}
void mul(double val) {
double pw = 1.0;
for (int k = 1; k < K; ++k) {
pw *= val;
sums[k] *= pw;
}
lz *= val;
}
};
int N, Q;
vector<double> P;
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
P.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%lf", &P[i]);
}
SegmentTreeRange<Node> seg(P);
for (; Q--; ) {
int O, L, R;
scanf("%d%d%d", &O, &L, &R);
--L;
if (O == 0) {
const auto res = seg.get(L, R);
double ans = 0.0;
for (int k = K; --k >= 1; ) {
ans -= res.sums[k] / k;
}
printf("%.15f\n", ans);
} else if (O == 1) {
double A;
scanf("%lf", &A);
seg.ch(L, R, &Node::mul, A);
} else {
assert(false);
}
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
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.255874176894808 -0.147343477320721
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 78ms
memory: 4156kb
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.647243684109742 -0.001447320472212 -0.092955641905498 -0.930783280600978 -0.064102393187695 -0.091664042818035 -0.047742692390557 -0.000850180901385 -0.031857810983800 -0.237312223564791 -0.517538000548581 -0.653499425352686 -0.301089175013262 -0.062422318721...
result:
ok 49679 numbers
Test #3:
score: 0
Accepted
time: 67ms
memory: 3856kb
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: 96ms
memory: 7432kb
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.253834831820501 -1.200913334851363 -4.833765227340955 -6.518246801155265 -4.753041328957258 -6.789314769064692 -1.015525863498104 -0.926283380228779 -6.034691179830515 -2.988201776056498 -7.726664675934902 -1.080315155619918 -6.670126007056702 -2.185412176424857 -5.157565170832170 -8.414249963713...
result:
ok 50073 numbers
Test #5:
score: 0
Accepted
time: 75ms
memory: 4312kb
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.487399644030272 -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: 100ms
memory: 7596kb
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.167327658154706 -2.821962220835863 -10.502585510475342 -3.230719999162611 -1.768827866133128 -0.159871392243549 -2.975950392983036 -1.308633471355218 -5.788947852625780 -5.924360231703480 -0.788549341490549 -5.900534211199788 -4.394460464419967 -5.878642061306237 -0.138563274535031 -4.8961708770...
result:
ok 50323 numbers
Test #7:
score: 0
Accepted
time: 66ms
memory: 3972kb
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: 74ms
memory: 4172kb
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: 73ms
memory: 4104kb
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: 172ms
memory: 47164kb
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.877193487795921 -1029.162795097455955 -1378.624193281004636 -549.981008825916092 -28.012906121054019 -384.732912600466136 -655.128153434662067 -2797.006316482722468 -1983.335814575911400 -84.414770988875276 -375.776877683192140 -280.496555044462355 -489.519765225729373 -129.109300731536820 -22...
result:
ok 49613 numbers
Test #11:
score: 0
Accepted
time: 162ms
memory: 47144kb
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.362565065430317 -2002.087598383695422 -1264.581555122988902 -2142.191415358371160 -921.904725167416814 -1278.346042021634503 -767.491091104402699 -1108.020485904935413 -16.371870248511399 -1277.685287751488659 -1354.669183618023681 -1697.427633785623811 -273.613936752037944 -460.84603726326315...
result:
ok 50100 numbers
Test #12:
score: 0
Accepted
time: 174ms
memory: 47068kb
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.022581650706357 -378.022060378676940 -1081.628503977202172 -748.395749165988150 -458.333239443408786 -33.195721923788334 -215.489351947579280 -869.046131845475429 -857.336573531472027 -528.264945883908695 -82.317316524439477 -635.337143042145840 -528.593031573697886 -63.117246443613276 -130.4530...
result:
ok 50141 numbers
Test #13:
score: 0
Accepted
time: 155ms
memory: 46976kb
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.357205966887765 -9.561645512996664 -11.282958571746560 -2099.148175745928256 -52.388852004831200 -0.772557619187410 -1081.887400860637626 -1237.071804974478482 -908.723274954048975 -1817.253229287674685 -1502.215328379160155 -518.655706846404428 -338.098220720479105 -153.194644583174124 -206.639...
result:
ok 50092 numbers
Test #14:
score: 0
Accepted
time: 176ms
memory: 47224kb
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.430420195169688 -643.412462888071559 -1.153318590109697 -147.929719746912781 -25.860100543911798 -126.604415025863545 -25.248674290088438 -569.764279621987725 -341.726492981082629 -64.081348282237002 -23.953878478447869 -161.155423412959948 -561.050205237398700 -584.592798668911087 -57.13009725...
result:
ok 50120 numbers
Test #15:
score: 0
Accepted
time: 167ms
memory: 47052kb
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.388200949892507 -1463.767087798203875 -219.385159599107169 -2603.725514523616766 -1640.079066967221252 -1376.036085014902255 -1403.700373050340659 -1244.217998907602350 -132.664771354797352 -51.228831000440991 -132.935242505912186 -1329.238435395070155 -1119.034630996487749 -0.849742950255133 ...
result:
ok 49632 numbers
Test #16:
score: 0
Accepted
time: 177ms
memory: 46936kb
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.040347155567588 -1222.114170660155878 -383.780093886088935 -656.532133314182943 -522.022740995800177 -181.471512505550862 -629.373502975126371 -379.849624212765605 -512.125576077680648 -300.047193422027362 -57.720869512297718 -9.263595573921970 -274.056441623741250 -365.724232395259548 -518.786...
result:
ok 50162 numbers
Extra Test:
score: 0
Extra Test Passed