QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714846#7329. Independent Eventshos_lyricAC ✓177ms47224kbC++147.5kb2024-11-06 08:37:512024-11-06 08:37:55

Judging History

This is the latest submission verdict.

  • [2024-11-06 08:37:55]
  • Judged
  • Verdict: AC
  • Time: 177ms
  • Memory: 47224kb
  • [2024-11-06 08:37:51]
  • Submitted

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