QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290601#5351. 游戏MoRanSky100 ✓321ms49888kbC++233.2kb2023-12-25 06:02:092023-12-25 06:02:10

Judging History

你现在查看的是最新测评结果

  • [2023-12-25 06:02:10]
  • 评测
  • 测评结果:100
  • 用时:321ms
  • 内存:49888kb
  • [2023-12-25 06:02:09]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 2e5 + 5;

int n, m;

double p[N], q[N];

char ty[4], op[N];

int st[N];

set<int> s;

struct Mat{
	double w[2][2];
	Mat operator * (const Mat &b) const {
		Mat c; 
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				c.w[i][j] = 0;
				for (int k = 0; k < 2; k++)
					c.w[i][j] += w[i][k] * b.w[k][j];
			}
		}
		return c;
	}
	Mat operator + (const Mat &b) const {
		Mat c; 
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				c.w[i][j] = w[i][j] + b.w[i][j];
			}
		}
		return c;
	}
} A[N];

struct Node{
	Mat s, v;
} t[N << 2];

Node inline merge(const Node &x, const Node &y, Mat w) {
	return (Node) { x.s * w * y.s, (x.s * w * y.v) + (x.v * w * y.s) };
}

double ans;

#define ls (p << 1)
#define rs (p << 1 | 1)

void build(int p, int l, int r) {
	if (l == r) {
		t[p].s.w[0][0] = t[p].s.w[1][1] = t[p].v.w[1][1] = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	t[p] = merge(t[ls], t[rs], A[mid + 1]);
}

Node query(int p, int l, int r, int x, int y) {
	if (x <= l && r <= y) return t[p];
	int mid = (l + r) >> 1;
	if (y <= mid) return query(ls, l, mid, x, y);
	if (x > mid) return query(rs, mid + 1, r, x, y);
	return merge(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y), A[mid + 1]);
}

double calc(int l, int r) {
	if (l + 1 == r) return 0;
	Node u = query(1, 0, n + 1, l, r);
	double z = u.s.w[st[l]][st[r]];
	double sum = u.v.w[st[l]][st[r]] - (st[l] + st[r]) * z;
	return sum / z;
}

void inline ins(int x, int c) {
	auto o = s.lower_bound(x);
	int R = *o;
	--o;
	int L = *o;
	s.insert(x);
	ans -= calc(L, R);
	st[x] = c;
	ans += calc(L, x);
	ans += calc(x, R);
	ans += st[x];
}

void inline del(int x) {
	ans -= st[x];
	s.erase(x);
	auto o = s.lower_bound(x);
	int R = *o;
	--o;
	int L = *o;
	ans -= calc(L, x);
	ans -= calc(x, R);
	st[x] = -1;
	ans += calc(L, R);
}

int main() {
	memset(st, -1, sizeof st);
	read(n), read(m); scanf("%s", ty);
	st[0] = st[n + 1] = 1;
	for (int i = 1; i <= n; i++) {
		scanf("%lf", p + i);
		if (i != 1) scanf("%lf", q + i);
	}
	p[n + 1] = q[n + 1] = 1;
	for (int i = 1; i <= n + 1; i++) {
		A[i].w[1][1] = p[i];
		A[i].w[1][0] = (1 - p[i]);
		A[i].w[0][1] = q[i];
		A[i].w[0][0] = (1 - q[i]);
	}
	s.insert(0), s.insert(n + 1);
	build(1, 0, n + 1);
	ans += calc(0, n + 1);
	while (m--) {
		int x; 
		scanf("%s", op); read(x);
		if (op[0] == 'a') {
			int c; read(c);
			ins(x, c);
		} else {
			del(x);
		}
		printf("%.6lf\n", ans);
	}
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 1ms
memory: 10072kb

input:

10 20 A
0.1828
0.8160 0.1626
0.6803 0.3812
0.8498 0.2954
0.2434 0.7401
0.8895 0.7153
0.9561 0.9367
0.0976 0.4951
0.0517 0.9206
0.6723 0.5409
add 7 1
add 3 0
add 10 0
add 2 1
del 2
del 3
add 4 0
add 6 0
del 7
del 4
add 1 0
del 10
add 4 1
add 8 1
del 1
add 2 1
del 2
del 8
add 1 1
del 6

output:

5.332953
4.591962
3.918397
5.150383
3.918397
4.659388
4.008240
2.945552
2.879156
3.765182
3.404707
4.081794
4.521568
4.344427
4.724627
5.843562
4.724627
4.901768
6.314612
7.219311

result:

ok 20 numbers

Test #2:

score: 5
Accepted
time: 1ms
memory: 9976kb

input:

10 20 A
0.1828
0.2747 0.6953
0.3592 0.0605
0.3693 0.1264
0.7730 0.4113
0.9563 0.1329
0.8865 0.7829
0.7515 0.9111
0.8138 0.1832
0.0006 0.1736
add 4 1
add 6 0
add 7 0
add 3 1
del 4
add 5 0
del 5
add 9 1
del 3
add 1 1
del 1
add 4 0
del 4
add 2 1
del 6
del 9
add 10 1
del 2
add 8 1
add 6 1

output:

6.262621
4.806361
4.213574
4.869954
3.983902
3.907667
3.983902
4.251657
3.124194
3.488988
3.124194
2.988894
3.124194
3.535619
4.322909
4.055153
4.057740
3.622282
3.923225
5.233838

result:

ok 20 numbers

Test #3:

score: 5
Accepted
time: 0ms
memory: 10088kb

input:

100 100 B
0.1828
0.9997 0.0001
0.9996 0.0001
0.0001 0.9994
0.9998 0.0003
0.0002 0.9996
0.9998 0.0007
0.0001 0.9999
0.9999 0.0003
0.0001 0.9999
0.9998 0.0001
0.9995 0.0002
0.9997 0.0001
0.9999 0.0001
0.0001 0.9995
0.0003 0.9997
0.0004 0.9998
0.0002 0.9996
0.0005 0.9996
0.0002 0.9998
0.9999 0.0003
0.9...

output:

47.026172
47.043233
46.934692
47.043233
61.723310
61.787019
49.765271
60.830224
58.562487
58.593242
60.077263
60.046509
53.203937
53.200549
54.294684
48.208170
53.959995
51.177858
56.333023
55.528551
45.120740
45.131494
45.392513
45.386634
45.392513
45.386581
45.376423
49.239198
53.577764
53.530949
...

result:

ok 100 numbers

Test #4:

score: 5
Accepted
time: 1ms
memory: 10048kb

input:

100 100 B
0.1828
0.9998 0.0006
0.9997 0.0003
0.9999 0.0002
0.0001 0.9993
0.0006 0.9997
0.0004 0.9995
0.9999 0.0006
0.9998 0.0002
0.9999 0.0005
0.0001 0.9997
0.9997 0.0001
0.0002 0.9998
0.0004 0.9997
0.0001 0.9996
0.9996 0.0004
0.9999 0.0001
0.9999 0.0001
0.9998 0.0002
0.9999 0.0005
0.9999 0.0001
0.9...

output:

46.056284
45.981661
45.981615
45.242400
52.735568
52.734064
45.240896
40.578224
45.522349
45.243232
48.718597
54.039466
53.981298
53.976946
56.921262
56.921280
56.921377
56.921186
56.921242
53.604624
56.921242
55.411470
55.444376
57.042326
59.713284
60.654382
62.654644
55.906938
53.906677
53.906696
...

result:

ok 100 numbers

Test #5:

score: 5
Accepted
time: 5ms
memory: 10120kb

input:

1000 5000 A
0.1828
0.9997 0.0001
0.9999 0.0005
0.9996 0.0003
0.0001 0.9999
0.0001 0.9997
0.1247 0.2253
0.0002 0.9998
0.0001 0.9999
0.0002 0.9995
0.9995 0.0002
0.0002 0.9997
0.0005 0.9999
0.9994 0.0002
0.0006 0.9999
0.9999 0.0002
0.0038 0.6732
0.0001 0.9998
0.0005 0.9998
0.9998 0.0002
0.9998 0.0003
0...

output:

503.424365
499.983955
493.639549
492.505301
491.792557
498.056885
494.274139
495.452704
494.429282
494.000585
494.429282
490.686928
493.707016
495.851040
492.265584
501.429124
500.098705
497.954681
499.285100
496.649846
495.368579
498.954034
494.594687
495.618100
495.192310
495.428762
494.364694
492...

result:

ok 5000 numbers

Test #6:

score: 5
Accepted
time: 2ms
memory: 10092kb

input:

1000 5000 A
0.1828
0.9998 0.0007
0.0002 0.9995
0.0001 0.9999
0.0002 0.9997
0.0004 0.9997
0.9999 0.0007
0.0004 0.9995
0.9999 0.0002
0.0002 0.9996
0.0005 0.9999
0.0002 0.9995
0.9999 0.0001
0.9996 0.0003
0.0001 0.9998
0.0002 0.9998
0.9999 0.0001
0.0003 0.9999
0.0001 0.9998
0.0001 0.9999
0.9999 0.0006
0...

output:

501.213036
500.358814
500.003228
493.953139
494.115425
494.470878
491.690639
492.544861
492.141648
492.008670
498.058750
498.191728
496.497231
496.900586
490.859026
488.882747
488.245618
489.939963
488.532939
491.723472
489.753387
491.723472
492.799906
490.756327
490.228900
492.272479
495.052718
499...

result:

ok 5000 numbers

Test #7:

score: 5
Accepted
time: 6ms
memory: 10316kb

input:

2000 5000 B
0.1828
0.9997 0.0002
0.0005 0.9998
0.9998 0.0004
0.0006 0.9999
0.0008 0.9999
0.0005 0.9997
0.0004 0.9998
0.9999 0.0001
0.9999 0.0001
0.0004 0.9998
0.9997 0.0001
0.0001 0.9999
0.9998 0.0002
0.9999 0.0001
0.0004 0.9997
0.0001 0.9995
0.0004 0.9996
0.9998 0.0005
0.9998 0.0002
0.9998 0.0003
0...

output:

1012.915897
991.593736
979.018209
978.148414
979.599559
983.551414
970.346216
969.462512
970.346216
969.424611
969.264422
969.264454
979.593241
974.958155
1000.067754
1001.656279
1018.438179
983.921399
978.243474
1011.968433
1011.968402
1012.255741
1003.056452
1001.467926
1007.884745
1008.988012
100...

result:

ok 5000 numbers

Test #8:

score: 5
Accepted
time: 6ms
memory: 10296kb

input:

2000 5000 B
0.1828
0.9997 0.0003
0.9996 0.0004
0.0001 0.9995
0.9997 0.0001
0.9998 0.0005
0.9995 0.0002
0.0002 0.9994
0.0006 0.9997
0.9999 0.0002
0.9996 0.0004
0.0002 0.9995
0.9993 0.0002
0.0001 0.9997
0.9993 0.0001
0.9999 0.0002
0.9996 0.0002
0.9999 0.0001
0.9997 0.0002
0.0006 0.9997
0.0001 0.9992
0...

output:

1018.865283
1008.214789
1011.531317
1008.214789
1011.629480
1010.764430
1011.952010
1019.388924
1014.843974
1019.388924
1001.816459
989.091831
989.303427
1002.028055
1002.616786
1003.180322
990.340360
996.389118
992.556806
997.281924
997.282371
996.987507
1000.361722
996.805823
1001.423920
1004.9431...

result:

ok 5000 numbers

Test #9:

score: 5
Accepted
time: 6ms
memory: 10256kb

input:

2000 5000 B
0.1829
0.0001 0.9999
0.9998 0.0007
0.9998 0.0007
0.9997 0.0004
0.9999 0.0001
0.0006 0.9999
0.0002 0.9997
0.9995 0.0003
0.9995 0.0002
0.9995 0.0004
0.0001 0.9996
0.9997 0.0005
0.0002 0.9994
0.0001 0.9994
0.0003 0.9998
0.0001 0.9999
0.0001 0.9995
0.0002 0.9993
0.9998 0.0001
0.0006 0.9998
0...

output:

1019.276093
1024.366948
1024.592832
1020.109744
1026.872003
1027.073370
1028.752265
1027.073370
1027.070868
1022.456603
1022.670144
1022.675401
1019.482513
1022.675401
1020.425705
1020.349261
1020.325044
1020.360278
1019.551613
1019.551417
1018.800238
1018.789964
1014.259499
1023.374754
1013.810217
...

result:

ok 5000 numbers

Test #10:

score: 5
Accepted
time: 2ms
memory: 10328kb

input:

2000 5000 C
0.1829
0.0003 0.9997
0.9993 0.0002
0.0002 0.9997
0.0002 0.9993
0.9998 0.0002
0.9998 0.0004
0.9999 0.0002
0.9999 0.0007
0.0001 0.9998
0.9999 0.0001
0.9999 0.0001
0.0002 0.9994
0.9996 0.0001
0.4323 0.1450
0.9996 0.0001
0.0002 0.9999
0.9999 0.0001
0.0002 0.9995
0.9996 0.0003
0.0005 0.9999
0...

output:

1006.388616
1006.820186
1005.798756
1006.820186
1005.845666
1006.820186
1007.512466
1006.820186
1005.849157
1006.820186
1008.338422
1006.820186
1002.231638
1006.820186
1012.469551
1006.820186
1004.243011
1006.820186
1006.431121
1006.820186
1005.410792
1006.820186
1008.435347
1006.820186
1011.080901
...

result:

ok 5000 numbers

Test #11:

score: 5
Accepted
time: 207ms
memory: 13716kb

input:

9591 199770 B
0.8930
0.9996 0.0001
0.9997 0.0002
0.0002 0.9998
0.0002 0.9994
0.9997 0.0005
0.9996 0.0003
0.0004 0.9998
0.9994 0.0001
0.9996 0.0005
0.9997 0.0005
0.9995 0.0001
0.9995 0.0004
0.9996 0.0004
0.9997 0.0001
0.0003 0.9997
0.9997 0.0001
0.0004 0.9999
0.0001 0.9998
0.0002 0.9999
0.9997 0.0003...

output:

4811.727910
4783.258671
4784.418073
4781.089018
4781.972985
4754.879882
4783.119390
4783.707300
4783.711998
4777.624751
4787.909450
4786.798925
4784.096651
4783.991394
4784.283725
4778.015122
4776.055618
4777.918376
4777.841427
4777.719269
4804.628291
4778.192132
4778.195227
4786.629596
4781.500064
...

result:

ok 199770 numbers

Test #12:

score: 5
Accepted
time: 199ms
memory: 12888kb

input:

9591 192400 B
0.4043
0.0002 0.9993
0.9996 0.0001
0.0001 0.9998
0.9999 0.0008
0.0002 0.9998
0.9999 0.0001
0.9995 0.0001
0.0005 0.9997
0.9997 0.0002
0.0003 0.9996
0.0003 0.9997
0.0002 0.9999
0.0001 0.9994
0.0008 0.9999
0.9993 0.0001
0.9999 0.0005
0.9997 0.0002
0.0001 0.9999
0.0001 0.9997
0.9998 0.0002...

output:

4819.821848
4808.319320
4795.805687
4799.025441
4794.706333
4795.212296
4794.463293
4800.642181
4800.661032
4803.517513
4791.100729
4790.664572
4785.068535
4785.066145
4797.940876
4796.574628
4794.014680
4794.324230
4753.202537
4750.869743
4750.809721
4748.818189
4755.440621
4755.444240
4749.058857
...

result:

ok 192400 numbers

Test #13:

score: 5
Accepted
time: 194ms
memory: 13552kb

input:

9591 195031 B
0.9155
0.9996 0.0002
0.9999 0.0003
0.9998 0.0001
0.9999 0.0001
0.9994 0.0003
0.9996 0.0001
0.9997 0.0003
0.9999 0.0001
0.9992 0.0001
0.0002 0.9996
0.0001 0.9995
0.0003 0.9998
0.0004 0.9997
0.9998 0.0004
0.9999 0.0001
0.0007 0.9998
0.0005 0.9999
0.0001 0.9999
0.9997 0.0003
0.9999 0.0001...

output:

4819.210538
4819.927756
4820.133929
4820.494480
4816.038594
4797.851917
4805.858919
4805.876880
4804.185258
4804.217742
4804.223870
4804.205808
4804.370705
4804.390192
4813.364464
4808.117280
4789.970815
4787.294114
4787.318941
4789.387431
4787.093568
4787.084344
4787.084674
4785.741831
4785.747708
...

result:

ok 195031 numbers

Test #14:

score: 5
Accepted
time: 213ms
memory: 49836kb

input:

195914 198831 C
0.4267
0.9999 0.0001
0.9998 0.0002
0.9999 0.0002
0.9998 0.0001
0.0001 0.9995
0.9995 0.0002
0.0006 0.9999
0.0003 0.9999
0.9999 0.0003
0.0001 0.9995
0.0004 0.9998
0.0001 0.9994
0.9995 0.0001
0.0001 0.9998
0.0002 0.9999
0.9999 0.0002
0.0003 0.9997
0.0004 0.9995
0.0005 0.9997
0.9999 0.00...

output:

97891.037624
97887.221967
97882.084699
97887.221967
97883.949090
97887.221967
97902.406779
97887.221967
97879.835310
97887.221967
97902.700183
97887.221967
97881.735538
97887.221967
97882.176103
97887.221967
97893.800714
97887.221967
97886.843092
97887.221967
97886.683373
97887.221967
97882.882341
9...

result:

ok 198831 numbers

Test #15:

score: 5
Accepted
time: 201ms
memory: 49888kb

input:

195914 195146 C
0.9379
0.0003 0.9996
0.0001 0.9997
0.9999 0.0002
0.0001 0.9997
0.9999 0.0002
0.9999 0.0001
0.0003 0.9996
0.9996 0.0002
0.9996 0.0004
0.0004 0.9999
0.0001 0.9995
0.0006 0.9997
0.0003 0.9998
0.9994 0.0002
0.9997 0.0002
0.0003 0.9997
0.9994 0.0001
0.0004 0.9996
0.0001 0.9999
0.9995 0.00...

output:

98067.840355
98063.137822
98062.994472
98063.137822
98049.982882
98063.137822
98068.425782
98063.137822
98064.103727
98063.137822
98066.853475
98063.137822
98061.437365
98063.137822
98063.732637
98063.137822
98058.471914
98063.137822
98064.130788
98063.137822
98057.681386
98063.137822
98056.023542
9...

result:

ok 195146 numbers

Test #16:

score: 5
Accepted
time: 296ms
memory: 47836kb

input:

195914 197119 D
0.2048
0.0001 0.9999
0.0004 0.9997
0.9999 0.0002
0.0003 0.9997
0.9999 0.0001
0.0001 0.9999
0.0004 0.9997
0.0002 0.9993
0.0005 0.9996
0.9999 0.0002
0.9999 0.0001
0.9996 0.0003
0.9999 0.0003
0.9998 0.0006
0.9994 0.0002
0.9997 0.0006
0.0003 0.9999
0.9993 0.0001
0.9999 0.0003
0.9998 0.00...

output:

97919.840662
97919.944746
97919.897013
97917.999597
97915.365641
97910.205656
97906.291117
97908.925073
97889.960673
97908.925073
97908.972805
97908.868721
97909.299472
97902.033678
97901.602927
97905.517465
97894.384018
97896.963345
97898.410895
97896.963345
97908.096792
97902.621733
97897.904775
9...

result:

ok 197119 numbers

Test #17:

score: 5
Accepted
time: 306ms
memory: 49864kb

input:

195914 198435 D
0.7159
0.9998 0.0004
0.0002 0.9995
0.9999 0.0002
0.9995 0.0002
0.0003 0.9996
0.0003 0.9998
0.9993 0.0001
0.9999 0.0002
0.0001 0.9996
0.9999 0.0001
0.9999 0.0001
0.9992 0.0001
0.9998 0.0001
0.0003 0.9998
0.9999 0.0001
0.0002 0.9998
0.0002 0.9998
0.9995 0.0002
0.0001 0.9995
0.9996 0.00...

output:

97917.739318
97923.566157
97925.250117
97923.566157
97927.393425
97927.494548
97923.667280
97917.840441
97917.232632
97917.840441
97914.430267
97916.029348
97915.928225
97911.992001
97891.872974
97896.824465
97899.360397
97919.479424
97916.738232
97915.139151
97912.603219
97932.542216
97927.590725
9...

result:

ok 198435 numbers

Test #18:

score: 5
Accepted
time: 321ms
memory: 47816kb

input:

195915 195407 A
0.9827
0.9998 0.0007
0.9999 0.0002
0.9999 0.0002
0.9998 0.0007
0.0002 0.9996
0.0003 0.9998
0.9994 0.0002
0.9998 0.0003
0.0002 0.9996
0.0001 0.9992
0.9995 0.0002
0.0006 0.9998
0.9999 0.0001
0.9997 0.0001
0.9997 0.0001
0.0005 0.9998
0.9995 0.0004
0.9998 0.0004
0.9999 0.0008
0.9999 0.00...

output:

98061.411909
98068.700578
98073.254256
98067.498728
98068.258059
98069.183943
98072.855033
98072.403850
98072.783172
98087.970357
98090.468862
98097.775207
98105.665814
98105.311399
98102.177175
98095.387440
98097.340768
98086.258237
98089.233592
98089.570111
98098.277500
98081.233912
98079.586934
9...

result:

ok 195407 numbers

Test #19:

score: 5
Accepted
time: 308ms
memory: 47836kb

input:

195915 197381 A
0.2496
0.9999 0.0003
0.9996 0.0002
0.0001 0.9999
0.0001 0.9998
0.9999 0.0004
0.0003 0.9998
0.9995 0.0003
0.0003 0.9995
0.9995 0.0003
0.9998 0.0005
0.9998 0.0001
0.0005 0.9998
0.0001 0.9992
0.9999 0.0003
0.9994 0.0001
0.0002 0.9999
0.0002 0.9996
0.9996 0.0002
0.0002 0.9999
0.9999 0.00...

output:

98089.806084
98090.102401
98087.560397
98088.964999
98086.117281
98108.804112
98110.612097
98110.403056
98114.894020
98114.846606
98114.145140
98114.460908
98083.930055
98082.121094
98093.745076
98100.735451
98099.261814
98080.578016
98075.687725
98073.973263
98070.361616
98071.393199
98072.440375
9...

result:

ok 197381 numbers

Test #20:

score: 5
Accepted
time: 321ms
memory: 47900kb

input:

195915 199354 A
0.5164
0.9995 0.0001
0.9999 0.0001
0.0001 0.9999
0.0003 0.9999
0.9999 0.0003
0.0002 0.9997
0.9996 0.0005
0.9998 0.0001
0.0004 0.9995
0.0003 0.9997
0.0006 0.9999
0.9997 0.0003
0.9995 0.0002
0.0001 0.9998
0.9999 0.0001
0.9995 0.0002
0.9998 0.0001
0.0004 0.9999
0.9998 0.0004
0.9996 0.00...

output:

97917.942344
97913.595375
97907.913024
97909.594476
97909.772792
97907.619040
97904.566160
97906.911172
97902.517238
97902.655074
97910.055523
97918.623721
97901.127214
97900.521858
97894.284806
97902.664576
97894.498341
97894.498456
97896.050850
97902.630105
97924.652260
97909.286947
97909.222967
9...

result:

ok 199354 numbers

Extra Test:

score: 0
Extra Test Passed