hi everyone :) i was working on #304 contest (PB D) and it seems like it doesn't work for cin and cout and u should use scanf and printf (which i really dont like to use ) finally even with them i couldn't get AC and can u tell me whats wrong with my code ? or if the algorithm is completely wrong ? thanks :) my code 11371801
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 9 | orz | 145 |
| 10 | pajenegod | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 07.06.2024 07:30:58 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
can you explain briefly your algorithm?
my dynamic array res[] counts the number of prime factors in each number . then we count the sum of all them from b + 1, b + 2, ... , a
then i guess you should use prefix sum to get your queries in O(1) time
im sorry i dont know how to use prefix sum
just add a loop in which you do this operation res[i] +=res[i-1] then the query for [b,a] will just be the difference res[a]-res[b-1] (you can google it its easy to understand)
This for loop is executed in every test case ... There are 10^6 test cases per file and this loop is O(5*10^6) ... That makes a total of 10^12 which is impossible to run in time.
You can use prefix sum to avoid this.
yeah you are right, but i dont know how to do that. can explain a little more about prefix sum ?
You need to get the sum of a elements in an array 'A' in range from L to R.
Prefix sum can get you the answer in O(1) with O(n) pre-computation.
Make a new sum array 'S' where S[i] = A[0] + A[1] + ... + A[i];
Now to get sum(L, R) = S[R] — S[L — 1]