QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812022#7329. Independent Events464zzyxAC ✓691ms108100kbC++142.0kb2024-12-13 10:47:042024-12-13 10:47:05

Judging History

This is the latest submission verdict.

  • [2024-12-13 10:47:05]
  • Judged
  • Verdict: AC
  • Time: 691ms
  • Memory: 108100kb
  • [2024-12-13 10:47:04]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define deb(x) cerr<<"deb:"<<__LINE__<<" "<<#x<<"="<<x<<"\n"
//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
inline ll read()
{
	ll sum=0,l=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')l=-1;c=getchar();}
	while(isdigit(c)){sum=(sum<<1)+(sum<<3)+(c^48);c=getchar();}
	return sum*l;
}
const ll n=20;
long double c[100100],tl[400100],tr[400100],ts[21][400100],tg[400100];
void Update(ll x)
{
	for(ll i=1;i<=n;i++)ts[i][x]=ts[i][x*2]+ts[i][x*2+1];
}
void upd(ll x,long double y)
{
	tg[x]*=y;
	long double now=y;
	for(ll i=1;i<=n;i++)
	{
		ts[i][x]*=now;
		now*=y;
	}
}
void Push(ll x)
{
	if(tg[x]!=1)
	{
		upd(x*2,tg[x]);
		upd(x*2+1,tg[x]);
		tg[x]=1;
	}
}
void Build(ll x,ll l,ll r)
{
	tl[x]=l;
	tr[x]=r;
	tg[x]=1;
	if(l==r)
	{
		c[l]=-c[l];
		long double now=c[l];
		for(ll i=1;i<=n;i++)
		{
			ts[i][x]=now/i;
			now*=c[l];
		}
		return;
	}
	ll mid=(l+r)/2;
	Build(x*2,l,mid);
	Build(x*2+1,mid+1,r);
	Update(x);
}
void Add(ll x,ll l,ll r,long double y)
{
	if(l<=tl[x]&&tr[x]<=r)
	{
		upd(x,y);
		return;
	}
	Push(x);
	ll mid=(tl[x]+tr[x])/2;
	if(l<=mid)Add(x*2,l,r,y);
	if(mid<r)Add(x*2+1,l,r,y);
	Update(x);
}
long double Query(ll x,ll l,ll r)
{
	if(l<=tl[x]&&tr[x]<=r)
	{
		long double res=0;
		ll pl=1;
		for(ll i=1;i<=n;i++)
		{
			res+=ts[i][x]*pl;
			pl*=-1;
		}
		return res;
	}
	Push(x);
	ll mid=(tl[x]+tr[x])/2;
	if(mid<l)return Query(x*2+1,l,r);
	else if(r<=mid)return Query(x*2,l,r);
	else return Query(x*2,l,r)+Query(x*2+1,l,r);
}
int main()
{
	ll a;
	while(cin>>a)
	{
		ll b=read();
		for(ll i=1;i<=a;i++)cin>>c[i];
		Build(1,1,a);
		for(ll i=1;i<=b;i++)
		{
			ll op=read(),d=read(),e=read();
			if(op==1)
			{
				long double f;
				cin>>f;
				Add(1,d,e,f); 
			}
			else
			{
				printf("%.20Lf\n",Query(1,d,e));
			}
		}
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 51124kb

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.16021487727848474649
-0.25587417689480757314
-0.14734347732072094072

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 178ms
memory: 52948kb

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.00094044207705666747
-0.17285693984128141989
-0.64724368410974252941
-0.00144732047221210144
-0.09295564190549821453
-0.93078328060097830995
-0.06410239318769475523
-0.09166404281803549134
-0.04774269239055688012
-0.00085018090138477359
-0.03185781098379997929
-0.23731222356479127256
-0.517538000...

result:

ok 49679 numbers

Test #3:

score: 0
Accepted
time: 101ms
memory: 50920kb

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.11234334353646578592
-0.06540972096058839847
-0.00070024511439339197
-0.00079031221444377012
-0.00042008822470378185
-0.03031012007523892018
-0.22314667967829175992
-0.23039835923016496016
-0.23109860434455835215
-0.06119075875847016149
-0.03442884130322685173
-0.19239907802427020312
-0.041068196...

result:

ok 49929 numbers

Test #4:

score: 0
Accepted
time: 275ms
memory: 55268kb

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.25383483182050153946
-1.20091333485136244632
-4.83376522734095516714
-6.51824680115526732243
-4.75304132895725867059
-6.78931476906469353336
-1.01552586349810384039
-0.92628338022877922461
-6.03469117983051598925
-2.98820177605649897460
-7.72666467593490401480
-1.08031515561991832831
-6.670126007...

result:

ok 50073 numbers

Test #5:

score: 0
Accepted
time: 167ms
memory: 51156kb

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.39563575857451233688
-0.67651661449835881799
-0.43381925917076002175
-0.33688849311982054630
-0.51037638189291524977
-0.03821502920540667698
-0.48739964403027150356
-0.22987323399959656881
-0.04415067969302214514
-0.14116948919146619224
-0.04044274492071074475
-0.05616189746191510936
-0.055121665...

result:

ok 50134 numbers

Test #6:

score: 0
Accepted
time: 274ms
memory: 55448kb

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.16732765815470480864
-2.82196222083586208346
-10.50258551047534144249
-3.23071999916261102430
-1.76882786613312751613
-0.15987139224354854910
-2.97595039298303619120
-1.30863347135521788239
-5.78894785262577911715
-5.92436023170347935991
-0.78854934149054881082
-5.90053421119978635263
-4.3944604...

result:

ok 50323 numbers

Test #7:

score: 0
Accepted
time: 129ms
memory: 51056kb

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.00348606928483182055
-0.00917712698287607293
-0.01166816563077832923
-0.11610460009743240038
-0.15541924783669570662
-0.25469589037010790836
-0.20509401924998587526
-0.31908848562863585517
-0.16627666208553031627
-0.07394133948551061980
-0.16531703634409425299
-0.02458204174678989507
-0.276475511...

result:

ok 50228 numbers

Test #8:

score: 0
Accepted
time: 165ms
memory: 50936kb

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.31699232564564253588
-0.58711881037315517010
-0.13350233560470561415
-2.30498090527367314388
-0.56817735856468091848
-1.29396423026600651605
-0.60382948288306821476
-0.45109343457771459537
-1.12574399851044647551
-0.69099610135258150993
-0.25534458060503799858
-0.92413000803156819583
-0.787400371...

result:

ok 50183 numbers

Test #9:

score: 0
Accepted
time: 162ms
memory: 51068kb

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.01905244538762502696
-0.31389354357469915970
-0.04210542317925456794
-0.42539259998942735810
-0.39728466243264603413
-0.32440089264736406138
-0.25618900114587178104
-0.16803179341778992978
-0.25344894948787393915
-0.44975065637923135258
-0.40578184638229122661
-0.13617961500067288471
-0.014801282...

result:

ok 50055 numbers

Test #10:

score: 0
Accepted
time: 651ms
memory: 106776kb

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.87719348779603323329
-1029.16279509745589604286
-1378.62419328100438375984
-549.98100882591601612503
-28.01290612105401596661
-384.73291260046610579026
-655.12815343466207562706
-2797.00631648272255569410
-1983.33581457591114804995
-84.41477098887527977938
-375.77687768319210959156
-280.496555...

result:

ok 49613 numbers

Test #11:

score: 0
Accepted
time: 687ms
memory: 106332kb

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.36256506543033206746
-2002.08759838369553674120
-1264.58155512298907363622
-2142.19141535837138179410
-921.90472516741695419018
-1278.34604202163462938202
-767.49109110440283887389
-1108.02048590493536728285
-16.37187024851140604992
-1277.68528775148873743994
-1354.66918361802387504866
-1697.4...

result:

ok 50100 numbers

Test #12:

score: 0
Accepted
time: 632ms
memory: 108100kb

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.02258165070635596329
-378.02206037867693402821
-1081.62850397720207140662
-748.39574916598822240665
-458.33323944340885819360
-33.19572192378833233248
-215.48935194757931546605
-869.04613184547555870818
-857.33657353147230956170
-528.26494588390889101115
-82.31731652443946921360
-635.33714304214...

result:

ok 50141 numbers

Test #13:

score: 0
Accepted
time: 674ms
memory: 99804kb

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.35720596688776683810
-9.56164551299666379183
-11.28295857174655860040
-2099.14817574592850513149
-52.38885200483119809756
-0.77255761918741043412
-1081.88740086063775192038
-1237.07180497447865175076
-908.72327495404919223132
-1817.25322928767482411061
-1502.21532837916023450653
-518.65570684640...

result:

ok 50092 numbers

Test #14:

score: 0
Accepted
time: 691ms
memory: 101504kb

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.43042019516965560055
-643.41246288807154429801
-1.15331859010969685971
-147.92971974691278885805
-25.86010054391179692826
-126.60441502586354837329
-25.24867429008843812410
-569.76427962198778132130
-341.72649298108264270812
-64.08134828223698813143
-23.95387847844787018725
-161.155423412959950...

result:

ok 50120 numbers

Test #15:

score: 0
Accepted
time: 658ms
memory: 105844kb

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.38820094989238196348
-1463.76708779820387795745
-219.38515959910715154291
-2603.72551452361695423221
-1640.07906696722125872157
-1376.03608501490207816076
-1403.70037305034088748190
-1244.21799890760247508936
-132.66477135479736207402
-51.22883100044099508735
-132.93524250591221350093
-1329.23...

result:

ok 49632 numbers

Test #16:

score: 0
Accepted
time: 672ms
memory: 103468kb

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.04034715556756507393
-1222.11417066015589028005
-383.78009388608891200301
-656.53213331418290782393
-522.02274099580022653777
-181.47151250555086346439
-629.37350297512632019137
-379.84962421276565858186
-512.12557607768060496944
-300.04719342202733620151
-57.72086951229771571714
-9.26359557392...

result:

ok 50162 numbers

Extra Test:

score: 0
Extra Test Passed