Codeforced Round #624 (Div. 3) Problem C O(n) solution TLEs

Problem Link :-
Submission Link :-

This is my code. It runs in O(n) but still gets TLE (it shouldn’t). So if anyone can check why my code TLEs that would be great.

using namespace std;
int main()
	int t;
	int siz = (2 * 1e5) + 20;
	cin >> t;
	while (t--)
		int n, m;

		cin >> n >> m;
		//scanf("%d %d", &n, &m);
		vector<int> k(siz, 0);
		string s;
		cin >> s;
		//scanf("%s", &s);
		for (int i = 0; i < m; i++)
			int x;
			cin >> x;
			//scanf("%d", &x);

		vector<long long int> h(26, 0);
		//vector<int> p(n, 0);

		long long int count = 1;

		for (int i = n - 1; i >= 0; i--)
			//p[i] += count;
			h[s[i] - 97] += count;
			count += k[i];

		for (int i = 0; i < 26; i++)
			cout << h[i] << " ";
			//printf("%d ", h[i]);
		cout << endl;

I stored the values of p in a map and ran a loop starting from the end of the string.
Then i increased the value of occurrence of that character by count. Then i incremented the value of count by the value of k[i] where k is the map which stores the amount of times the letters before index i are typed.

You are declaring vector of 210^5 and initializing it to 0 for each test case which will make it’s to complexity (210^5)*(10^4) .

You just need to create vector of size n.


In the constraints it is mentioned that sum of n overall testcases will not exceed 2*10^5.


I made the exact same mistake of declaring a vector with size 210^5.
@gourav_987 could you please elaborate how the time complexity becomes (2
10^5)*10^4 :slightly_smiling_face:

I think, Initializing vector with 0 value will take O(n) time complexity.

Shouldn’t be getting TLE for O(n) complexity then, should we?:neutral_face:

Read the output line carefully sum of all test cases doesn’t exceed 2 * 10^5.
If you keep creating an array of size 2 * 10^5 repeatedly
And since number of test cases are 10^4 it will TLE.
If you want to work globally simply declare resize array to n only not siz

Complexity for initializing is O(n) and in your case n=210^5 for each test case which will become O(nt).