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

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.

``````#include<iostream>
#include<vector>
using namespace std;
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
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);
k[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.

4 Likes

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

Thanks!

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

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?

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

n=2*10^5
t=10^4.