See my answer here.

As @betlista mentioned, since in this problem the numbers are up to 1000 you can use array instead of map in my solution and get `O(N + maxC)`

solution.

But it may appear that there are many tests with small `N`

in one test file. Say 100000 tests with N up to 5. Then this new solution may get TLE too since we always should iterate over array of size 1000. If I would be the author of this problem I would definitely create such test file

One way to avoid this is to use `O(N^2)`

brute-force for very small N, say N smaller that 45. For array of size 45 we have approximately 1000 pairs so brute-force will have the same time as counting solution. But then we can create a test file where all N are near 45 and T=10000 or higher and this new solution can also get TLE.

To avoid TLE for any evil possible tests we need another hacky array `mark[1000]`

that is initialized by zeros before reading tests. When we handle t-th test (t=1,2,…,T) `mark[Ci] == t`

if and only if `Ci`

appears in array `C[]`

of the current test. So we shouldn’t initialize it by zeros again. We also shouldn’t initialize array `cnt[1000]`

. The value `cnt[Ci]`

will be actual only if `mark[Ci] == t`

. Otherwise it may contains some garbage from the previous tests. Finally to make efficient loop for calculating the answer we should save all different values that we met during reading in some array.

So during reading of our array if we read number `Ci`

for which `mark[Ci] < t`

then it means that we did not meet this number in the array before. So we should assign `mark[Ci] = t`

, assign `cnt[Ci] = 0`

and add it to the list of unique values. And as in the previous solution we of course should do `cnt[Ci]++`

for each read `Ci`

. So the C++ code for this part may look as follows:

int mark[1000] = {0};
int cnt[1000] = {0};
int lst[1000];
scanf("%d", &T);
for (int t = 0; t < T; ++t) {
int X, N;
scanf("%d, %d", &X, &N);
int len = 0;
for (int i = 0; i < N; ++i) {
int Ci;
scanf("%d", &Ci);
if (mark[Ci] < t) {
cnt[Ci] = 0;
mark[Ci] = t;
list[len++] = Ci;
}
cnt[Ci]++;
}
//now lst contains all different values among C[i]
// compute the answer. see below
}

Loop for computing the answer also requires some careful consideration. Now we have list `lst[1000]`

that contains `len`

elements that are all unique values among our array. We iterate by this list and for the current value `val`

if `val == X-val`

than add `cnt[val] * (cnt[val]-1) / 2`

as described in my previous post. Otherwise in order to not count the same pair twice val should be greater than `X-val`

and `mark[X-val]`

should be equal to `t`

. Otherwise `cnt[X-val]`

can be some garbage value from the previous tests. So the code looks as follows:

typedef long long LL;
LL ans = 0;
for (int i = 0; i < len; ++i) {
int val = lst[i];
if(val == X - val) {
ans += LL(cnt[val]) * (cnt[val] - 1) / 2;
} else if(X - val < val && mark[X - val] == t) {
ans += LL(cnt[val]) * cnt[X - val];
}
}
printf("%lld\n", ans);

Alternatively you could check condition `X-val > val`

but then it may appear that `X-val >= 1000`

so next look up at `mark[X-val]`

will be incorrect in this case. So you should either make `mark`

of size `2001`

or to save memory check condition X-val < 1000. In any case the way described above is better.

This solution has complexity `O(N + min(N,maxC)) = O(N)`

.