Actually im learning prefix sum and trying to solve problems with it. Im trying this problem for a quite long time. I dont no why my code is not showing the right output. Can someone help? Thanks in advance. 87009522
№ | Пользователь | Рейтинг |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Actually im learning prefix sum and trying to solve problems with it. Im trying this problem for a quite long time. I dont no why my code is not showing the right output. Can someone help? Thanks in advance. 87009522
Название |
---|
u are using the same variable i in the nested loop(look at below code),u should replace it by j or something. And even doing so will result in TLE.
for(int i=0;i<n;i++) { cin >> srt >> en; mi=min(mi,srt); mx=max(mx,en); for(int i=srt;i<=en;i++){ arr[i]++; } }
Also u are putting 2 instead of k.
for(int i=mi;i<=mx;i++){ if(arr[i]>=2)ans[i]=++c; else ans[i]=c; }
In this line:
I think you mean to put k instead of 2. Also your algorithm is O(n^2) due to this part:
But you can easily improve it to $$$O(n)$$$ by using a difference array. You can read about it here: https://cses.fi/book/book.pdf and/or here: https://www.geeksforgeeks.org/difference-array-range-update-query-o1/