I solved this problem : They are everywhere using two pointer ,
but now i am trying to solve this problem using binary search . I am getting TLE on test 11 . Here is my code :
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 8 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.10.2026 02:58:30 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Your binary search is too expensive for it's purposes. For each iteration, you add element from i to mid in a set, which makes the complexity nlogn. and since you do the iteration log n times, it will be nlognlogn. and since you have a for loop from 1 to n for this, it will become n^2log^2n, which clearly is too high for n = 1e5.
How can i evaluate : number of distinct character from index i to index mid without inserting into set ? I did precalculation like partial sum ,but it does not work for some cases .
well there are a few ways, I will just suggest 2:
1) use 26 segment tree for each character and do a range sum query of that range and see if it is 1.
2) store the index of the character into 26 sorted array, and do a binary search for each character to see if within the range.
Do note that this will make your total complexity 26*nlog^2n, which may not be in the time limit.
Edit: something is wrong with me, you can do partial sum for each character and that will be O(1). silly me. I don't know why you say it do not work.
partial sum idea does not work for this case :
3
AaA
if partialSum[i] means number of distinct character from 1 to i . Then
partialSum[1]=1;
partialSum[2]=2;
partialSum[3]=2;
so for index i to j number of distinct character is partialSum[j] — partialSum[i-1] .
if i=2 , j=3 number of distinct character equals
partialSum[3] — partialSum[2-1]
=partialSum[3] — partialSum[2-1]
= 2 — 1
= 1 . which is wrong , because number of distinct character from 2 to 3 is 2 but it saying 1 .
you need a partial sum for each alphabet. and go through all alphabet in the string. so basically 52 partial sum if u have all 52 alphabet
I am not clear what you are saying , explanation please with an example .
for the above case: AaA
so when u check [1,2], just check that partial['a'][2]-partial['a'][0] is >= 1, and also partial['A'][2]-partial['A'][0] is >=1.
Thanks , got Accepted using your idea . :)
awesome. Glad to help :)