QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#290601 | #5351. 游戏 | MoRanSky | 100 ✓ | 321ms | 49888kb | C++23 | 3.2kb | 2023-12-25 06:02:09 | 2023-12-25 06:02:10 |
Judging History
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;
}
詳細信息
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