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
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 | tourist | 3690 |
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 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 145 |
Название |
---|
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/