QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76513#5474. Incredibly Cute Penguin ChicksXKErrorML 1354ms390788kbC++1.4kb2023-02-10 09:49:222023-02-10 09:49:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-10 09:49:24]
  • 评测
  • 测评结果:ML
  • 用时:1354ms
  • 内存:390788kb
  • [2023-02-10 09:49:22]
  • 提交

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...

output:


result: