QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#723613 | #5474. Incredibly Cute Penguin Chicks | emuach# | WA | 1001ms | 910308kb | C++17 | 2.7kb | 2024-11-07 23:12:24 | 2024-11-07 23:12:25 |
Judging History
answer
#include<bits/stdc++.h>
#define task ""
#define fi first
#define sc second
using namespace std;
using ll = long long;
const int N = 1000000, mod = 998244353, maxn = 2e6 + 10;
string s;
int dp[1000200], pre[1000200][4];
int id[255];
struct Node {
int left = 0;
int right = 0;
int val = 0;
Node() = default;
};
struct DynamicIT {
vector<Node> it;
DynamicIT() {
it.emplace_back();
it.emplace_back();
}
void Update(int r, int lo, int hi, int u, int val) {
if (u < lo || hi < u)
return;
if (lo == hi) {
(it[r].val += val) %= mod;
return;
}
int mid = (lo + hi)/2;
if (u <= mid) {
if (it[r].left == 0) {
it[r].left = it.size();
it.emplace_back();
}
Update(it[r].left, lo, mid, u, val);
}
else {
if (it[r].right == 0) {
it[r].right = it.size();
it.emplace_back();
}
Update(it[r].right, mid + 1, hi, u, val);
}
it[r].val = (it[it[r].left].val + it[it[r].right].val) % mod;
}
int Get(int r, int lo, int hi, int u, int v) {
if (r == 0 || v < lo || hi < u)
return 0;
if (u <= lo && hi <= v)
return it[r].val;
int mid = (lo + hi)/2;
int Left = Get(it[r].left, lo, mid, u, v);
int Right = Get(it[r].right, mid + 1, hi, u, v);
return (Left + Right) % mod;
}
} M[3][4][200002];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s;
int n = s.size();
s = " " + s;
id['I'] = 1;
id['C'] = 2;
id['P'] = 3;
dp[0] = 1;
M[0][1][N].Update(1, 0, N + N, N, 1);
M[0][2][N].Update(1, 0, N + N, N, 1);
M[1][2][N].Update(1, 0, N + N, N, 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= 3; ++j)
pre[i][j] = pre[i - 1][j] + (j == id[s[i]]);
(dp[i] += M[0][1][pre[i][1] - pre[i][2] + N].Get(1, 0, N + N, 0, pre[i][3] - pre[i][1] + N - 1)) %= mod;
(dp[i] += M[0][2][pre[i][1] - pre[i][3] + N].Get(1, 0, N + N, 0, pre[i][2] - pre[i][1] + N - 1)) %= mod;
(dp[i] += M[1][2][pre[i][2] - pre[i][3] + N].Get(1, 0, N + N, 0, pre[i][1] - pre[i][2] + N - 1)) %= mod;
M[0][1][pre[i][1] - pre[i][2] + N].Update(1, 0, N + N, pre[i][3] - pre[i][1] + N, dp[i]);
M[0][2][pre[i][1] - pre[i][3] + N].Update(1, 0, N + N, pre[i][2] - pre[i][1] + N, dp[i]);
M[1][2][pre[i][2] - pre[i][3] + N].Update(1, 0, N + N, pre[i][1] - pre[i][2] + N, dp[i]);
}
cout << dp[n];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 103ms
memory: 138652kb
input:
ICPC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 107ms
memory: 138540kb
input:
CCCIIIPPP
output:
69
result:
ok single line: '69'
Test #3:
score: 0
Accepted
time: 110ms
memory: 138772kb
input:
PICCICCIPPI
output:
24
result:
ok single line: '24'
Test #4:
score: 0
Accepted
time: 980ms
memory: 183128kb
input:
PCPPCCICPICPCPCPCCPPIPPPIICCCICPICCPPPIPCCCCICCIICPCCICCCPCICIPPIPIPIPPCCPCIPPCCPPCCIPPPIPPCIICIIIPPCIPPICPPICCPIICCCCCCCICPCCPPIPIPICPCIICPCCIPICCCPPCPIIICPCPPPIIIIICCCPCICCPPCPPCICIIIPIPICPCPPPPICPCPIPIIICCICPCIPPICCICPIIPPCCCIICPCPCCICCPICPPPPPPICCCIPCCICICIPICIIICCICPCIPIICPIPIIICCPCCIIPCCCCPIPI...
output:
216523282
result:
ok single line: '216523282'
Test #5:
score: 0
Accepted
time: 966ms
memory: 183260kb
input:
ICIPCICCIPIPIIPPCPCICICPCPCPIIICICPPICCICPIPCPCIIPPIPCCIPIPIPIICCICICCCIPPIIPCPPCIIICCICCCCCCPIPICCIPIICIICPIPCCICPPCCIPIPIICCCPCCIPCPPCCIIIIIPCIPIIPICIIIPIICCCIPPPIPICIIIICIIIPICIICPIPCCICIPCCIPICCCPPIPIIPICPPCPICIPIPPPPPCIPCCIPPICIPCICPCCCCPPIIIPCPICCICIPIIPICPIIIIPPPCPIIIPCCPPIIPPICPIIICCCPICPPIC...
output:
977504498
result:
ok single line: '977504498'
Test #6:
score: 0
Accepted
time: 955ms
memory: 188204kb
input:
PPCCCICCIPPICCPCCCCIPPPIICPIPIPPPPIPPPPPPCPIPICCPCCPICPIPPPIIPIPIIPPCCPIICPPIIIPPCCCIIPCCIPCCCCCCIIIPIPCICCIICIIICCCCPCCICPPCCPCCIPICCPPIIPIIPIPCIIPIIPPPCCIPCPCCICCIPICPPPCIPPIPCCPCPCCIPIICCIPCCIPPCPCIPICIICPPICIIICIPIIIIIPCCCPPIPPPCIICIIIPPCIPCIPCIICCCCPIPCPICICPIPCPPIPIPICCPCCCCPCIPCPPCCIPCCCCCPII...
output:
785880133
result:
ok single line: '785880133'
Test #7:
score: 0
Accepted
time: 966ms
memory: 179652kb
input:
ICIPCPIPCCCCCCCPCCPCCIPCPCPIPPCPIPCICPPIPPPPICPIIPPIICPICPICPPICICICCCIIPCPPCCICCCCPIICPPPIPIPCICPIPPPPCCPICPCPICICPPIIIICIICPPIPIIICCCCPIPIIPICCCIPCCPPCPPPPIIIIICIPCPCCPIIICICIPPCCPIPPCIIPCCCIIICPCIPCIIIIPCIIPCIICCCIPPIPPCIIPCICIPIIPICCICCPCPIICCCIPIICCCPIPPCCIIIICPPIICPCPCIPPPCPCICPPIPIPCCPIPPPIPI...
output:
687587235
result:
ok single line: '687587235'
Test #8:
score: 0
Accepted
time: 971ms
memory: 183848kb
input:
IICCCIPIIIIIPICIICPCPCIICCIIICCCIIPICICCCPCPCPPPIIPIPPICIICICIPIICCICCIIIPCIICCPPIPICIPPCPCPCPIICCIIICIPPICCICPPIPPPPICPCPIPCCCPCPCPPPPIICPCIIIIIIIPIPIICICCPPIIPPCICPCPCIPCPICPPPICCICIICPPIPPPIPIPIPPCIPPCIPPCPPPIICICCCPICIPPIPCCPIIPPCIPPICCIIIPPPPPIIPPICPCPCIPPCCPCIIIPPICCCIIIIICIPPIIICPCIIICPPCPCPP...
output:
698376687
result:
ok single line: '698376687'
Test #9:
score: 0
Accepted
time: 956ms
memory: 185672kb
input:
IIPICCCCIPPCCPICCIIPPPCIPCCPPIPIICICPCCIIPPCCCICICPPICCICPPIICIIPICPICIPPPPCPCCPIICCPPIPPCIIIIPICICICCIIPPCICCCCCPICPIPCPPCCPPICPICCCICCIPICCICPIICCPIPIPICCPPCCPCPCCPICCPICCCCCCIPIICPIPICICCPIIPIPICIICIPPPIPCICIPIPPICPICICPPICICCIPCIPPPCIPIIPPPIICICPPPIICCCPIIICIPIPPICICIPPPCCPCCIIPCCCPPPCPICPICPPCP...
output:
850857669
result:
ok single line: '850857669'
Test #10:
score: -100
Wrong Answer
time: 1001ms
memory: 910308kb
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
output:
565515926
result:
wrong answer 1st lines differ - expected: '709758735', found: '565515926'