QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#76513 | #5474. Incredibly Cute Penguin Chicks | XKError | ML | 1354ms | 390788kb | C++ | 1.4kb | 2023-02-10 09:49:22 | 2023-02-10 09:49:24 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 1000005
#define mod 998244353
using namespace std;
int n;
char s[maxn];
int a[3][maxn];
int f[maxn];
void $(int &x, int y) {
if ((x += y) >= mod) x -= mod;
}
unordered_map<int, int> t[3][maxn << 1];
void add(unordered_map<int, int> t[], int x, int k, int f) {
// cout<<"Add:"<<x<<" "<<k<<" "<<f<<endl;
x += n;
for (; x <= n * 2; x += x & -x) $(t[x][k], f);
}
int qry(unordered_map<int, int> t[], int x, int k) {
// cout<<"Qry:"<<x<<" "<<k<<endl;
x += n;
int res = 0;
for (; x; x -= x & -x) if (t[x].count(k)) $(res, t[x][k]);
return res;
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
f[0] = 1;
add(t[0], 0, 0, 1);
add(t[1], 0, 0, 1);
add(t[2], 0, 0, 1);
for (int i = 1; i <= n; i++) {
a[0][i] = a[0][i - 1] + (s[i] == 'C');
a[1][i] = a[1][i - 1] + (s[i] == 'I');
a[2][i] = a[2][i - 1] + (s[i] == 'P');
// cout<<a[0][i]<<" "<<a[1][i]<<" "<<a[2][i]<<endl;
$(f[i], qry(t[0], a[0][i] - a[1][i] - 1, a[1][i] - a[2][i]));
$(f[i], qry(t[1], a[1][i] - a[0][i] - 1, a[0][i] - a[2][i]));
$(f[i], qry(t[2], a[2][i] - a[0][i] - 1, a[0][i] - a[1][i]));
add(t[0], a[0][i] - a[1][i], a[1][i] - a[2][i], f[i]);
add(t[1], a[1][i] - a[0][i], a[0][i] - a[2][i], f[i]);
add(t[2], a[2][i] - a[0][i], a[0][i] - a[1][i], f[i]);
// cout<<f[i]<<endl;
}
printf("%d\n", f[n]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 87ms
memory: 331640kb
input:
ICPC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 108ms
memory: 331676kb
input:
CCCIIIPPP
output:
69
result:
ok single line: '69'
Test #3:
score: 0
Accepted
time: 93ms
memory: 331660kb
input:
PICCICCIPPI
output:
24
result:
ok single line: '24'
Test #4:
score: 0
Accepted
time: 1293ms
memory: 384956kb
input:
PCPPCCICPICPCPCPCCPPIPPPIICCCICPICCPPPIPCCCCICCIICPCCICCCPCICIPPIPIPIPPCCPCIPPCCPPCCIPPPIPPCIICIIIPPCIPPICPPICCPIICCCCCCCICPCCPPIPIPICPCIICPCCIPICCCPPCPIIICPCPPPIIIIICCCPCICCPPCPPCICIIIPIPICPCPPPPICPCPIPIIICCICPCIPPICCICPIIPPCCCIICPCPCCICCPICPPPPPPICCCIPCCICICIPICIIICCICPCIPIICPIPIIICCPCCIIPCCCCPIPI...
output:
216523282
result:
ok single line: '216523282'
Test #5:
score: 0
Accepted
time: 1321ms
memory: 384224kb
input:
ICIPCICCIPIPIIPPCPCICICPCPCPIIICICPPICCICPIPCPCIIPPIPCCIPIPIPIICCICICCCIPPIIPCPPCIIICCICCCCCCPIPICCIPIICIICPIPCCICPPCCIPIPIICCCPCCIPCPPCCIIIIIPCIPIIPICIIIPIICCCIPPPIPICIIIICIIIPICIICPIPCCICIPCCIPICCCPPIPIIPICPPCPICIPIPPPPPCIPCCIPPICIPCICPCCCCPPIIIPCPICCICIPIIPICPIIIIPPPCPIIIPCCPPIIPPICPIIICCCPICPPIC...
output:
977504498
result:
ok single line: '977504498'
Test #6:
score: 0
Accepted
time: 1311ms
memory: 390788kb
input:
PPCCCICCIPPICCPCCCCIPPPIICPIPIPPPPIPPPPPPCPIPICCPCCPICPIPPPIIPIPIIPPCCPIICPPIIIPPCCCIIPCCIPCCCCCCIIIPIPCICCIICIIICCCCPCCICPPCCPCCIPICCPPIIPIIPIPCIIPIIPPPCCIPCPCCICCIPICPPPCIPPIPCCPCPCCIPIICCIPCCIPPCPCIPICIICPPICIIICIPIIIIIPCCCPPIPPPCIICIIIPPCIPCIPCIICCCCPIPCPICICPIPCPPIPIPICCPCCCCPCIPCPPCCIPCCCCCPII...
output:
785880133
result:
ok single line: '785880133'
Test #7:
score: 0
Accepted
time: 1261ms
memory: 380428kb
input:
ICIPCPIPCCCCCCCPCCPCCIPCPCPIPPCPIPCICPPIPPPPICPIIPPIICPICPICPPICICICCCIIPCPPCCICCCCPIICPPPIPIPCICPIPPPPCCPICPCPICICPPIIIICIICPPIPIIICCCCPIPIIPICCCIPCCPPCPPPPIIIIICIPCPCCPIIICICIPPCCPIPPCIIPCCCIIICPCIPCIIIIPCIIPCIICCCIPPIPPCIIPCICIPIIPICCICCPCPIICCCIPIICCCPIPPCCIIIICPPIICPCPCIPPPCPCICPPIPIPCCPIPPPIPI...
output:
687587235
result:
ok single line: '687587235'
Test #8:
score: 0
Accepted
time: 1261ms
memory: 385084kb
input:
IICCCIPIIIIIPICIICPCPCIICCIIICCCIIPICICCCPCPCPPPIIPIPPICIICICIPIICCICCIIIPCIICCPPIPICIPPCPCPCPIICCIIICIPPICCICPPIPPPPICPCPIPCCCPCPCPPPPIICPCIIIIIIIPIPIICICCPPIIPPCICPCPCIPCPICPPPICCICIICPPIPPPIPIPIPPCIPPCIPPCPPPIICICCCPICIPPIPCCPIIPPCIPPICCIIIPPPPPIIPPICPCPCIPPCCPCIIIPPICCCIIIIICIPPIIICPCIIICPPCPCPP...
output:
698376687
result:
ok single line: '698376687'
Test #9:
score: 0
Accepted
time: 1354ms
memory: 387152kb
input:
IIPICCCCIPPCCPICCIIPPPCIPCCPPIPIICICPCCIIPPCCCICICPPICCICPPIICIIPICPICIPPPPCPCCPIICCPPIPPCIIIIPICICICCIIPPCICCCCCPICPIPCPPCCPPICPICCCICCIPICCICPIICCPIPIPICCPPCCPCPCCPICCPICCCCCCIPIICPIPICICCPIIPIPICIICIPPPIPCICIPIPPICPICICPPICICCIPCIPPPCIPIIPPPIICICPPPIICCCPIIICIPIPPICICIPPPCCPCCIIPCCCPPPCPICPICPPCP...
output:
850857669
result:
ok single line: '850857669'
Test #10:
score: -100
Memory Limit Exceeded
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...