Submission #868998

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868998	2023-11-02T19:52:06 Z	Cyber_Wolf	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	13 ms	6188 KB

Main

// Problem: Writing Numbers
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1086
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

#define lg long long 

const lg N = 2e5+5;

vector<lg> a[27];
lg loc[N], bit[N], m;

lg get(lg idx)
{
	lg ans = 0;
	while(idx)
	{
		ans += bit[idx];
		idx -= (idx&(-idx));
	}
	return ans;
}

void upd(lg idx)
{
	while(idx <= m)
	{
		bit[idx]++;
		idx += (idx&(-idx));
	}
}

int main()
{
	lg n;
	string s;
	cin >> n >> s;
	m = 2*n;
	for(int i = 0; i < n*2; i++)
	{
		a[s[i]-'a'].push_back(i);
	}
	for(int i = 0; i < 26; i++)
	{
		lg x = a[i].size()/2;
		for(int j = 0; j < x; j++)
		{
			loc[a[i][j]] = -1;
			loc[a[i][j+x]] = 1;
		}
		a[i].clear();
	}
	string c = "", d = "";
	lg ans = 0;
	for(int i = 0; i < n*2; i++)	
	{
		if(loc[i] == -1)	c += s[i], ans += d.size(), loc[i] = c.size()-1;
		else	d += s[i], loc[i] = d.size()+n-1;
	}
	s = c+d;
	for(int i = 0; i < n*2; i++)
	{
		a[s[i]-'a'].push_back(i);
	}
	for(int i = 0; i < 26; i++)
	{
		lg x = a[i].size()/2;
		for(int j = 0; j < x; j++)
		{
			loc[a[i][j]] = a[i][j];
			loc[a[i][j+x]] = loc[a[i][j]]+n;
		}
	}
	for(int i = 2*n-1; i+1; i--)
	{
		ans += get(loc[i]+1);
		upd(loc[i]+1);
	}
	cout << ans << '\n';
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	3 ms	3476 KB	Output is correct
3	Correct	7 ms	4580 KB	Output is correct
4	Correct	12 ms	5920 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	3 ms	3476 KB	Output is correct
3	Correct	7 ms	4580 KB	Output is correct
4	Correct	12 ms	5920 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	3 ms	3476 KB	Output is correct
3	Correct	7 ms	4580 KB	Output is correct
4	Correct	12 ms	5920 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	11 ms	6184 KB	Output is correct
7	Correct	11 ms	6124 KB	Output is correct
8	Correct	11 ms	5932 KB	Output is correct
9	Correct	11 ms	6128 KB	Output is correct
10	Correct	10 ms	6184 KB	Output is correct
11	Correct	13 ms	5984 KB	Output is correct
12	Correct	10 ms	5868 KB	Output is correct
13	Correct	10 ms	5872 KB	Output is correct
14	Correct	10 ms	5944 KB	Output is correct
15	Correct	10 ms	5944 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	3 ms	3476 KB	Output is correct
3	Correct	7 ms	4580 KB	Output is correct
4	Correct	12 ms	5920 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	11 ms	6184 KB	Output is correct
11	Correct	11 ms	6124 KB	Output is correct
12	Correct	11 ms	5932 KB	Output is correct
13	Correct	11 ms	6128 KB	Output is correct
14	Correct	10 ms	6184 KB	Output is correct
15	Correct	13 ms	5984 KB	Output is correct
16	Correct	10 ms	5868 KB	Output is correct
17	Correct	10 ms	5872 KB	Output is correct
18	Correct	10 ms	5944 KB	Output is correct
19	Correct	10 ms	5944 KB	Output is correct
20	Correct	0 ms	2396 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	1 ms	2396 KB	Output is correct
24	Correct	1 ms	2396 KB	Output is correct
25	Correct	1 ms	2396 KB	Output is correct
26	Correct	1 ms	2396 KB	Output is correct
27	Correct	1 ms	2396 KB	Output is correct
28	Correct	1 ms	2396 KB	Output is correct
29	Correct	1 ms	2396 KB	Output is correct
30	Correct	1 ms	2396 KB	Output is correct
31	Correct	1 ms	2396 KB	Output is correct
32	Correct	12 ms	6124 KB	Output is correct
33	Correct	12 ms	6124 KB	Output is correct
34	Correct	13 ms	6124 KB	Output is correct
35	Correct	11 ms	6188 KB	Output is correct
36	Correct	11 ms	6188 KB	Output is correct
37	Correct	10 ms	5936 KB	Output is correct
38	Correct	10 ms	5928 KB	Output is correct
39	Correct	10 ms	5940 KB	Output is correct
40	Correct	10 ms	5944 KB	Output is correct
41	Correct	10 ms	5992 KB	Output is correct