| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
i used mos algo for this problem but got TLE on case 43,38 etc;;; i can't get whats wrong with me,,,i saw a solve my type but i got TLE
problem link : http://codeforces.net/contest/86/problem/D
my code : http://codeforces.net/contest/86/submission/19782537
thanx in advance
Advice
Let me begin with a simple advice. When you are going to ask someone to look at your code in order to help you, just don't write such an ugly code! Really, reading those defines is awful if you are not used to them.
My experience with this problem
When I was solving the problem, I was also getting TLE in the beginning but I managed to get accepted with some optimizations (I see I have a solution running in 1.3 seconds). So here is how I managed to make your code get accepted...
Optimization 1 — Storing the block for each query in the structure, instead of computing it every time we compare two queries (TL #51)
Well, it is well known that division is a slow operation, so it's better to do it O(N) instead of O(NlogN) times — http://codeforces.net/contest/86/submission/19783742.
Optimization 2 — Dividing unsigned instead of signed integers (Lucky accepted)
I think it's not so well known but division (and modulo operations) are faster on unsigned integers, so I just replaced int with unsigned everywhere I need to use division and it managed to get accepted very luckily — http://codeforces.net/contest/86/submission/19783819.
Optimization 3 — The simplest one — using int instead of long long for cnt[] (Not so lucky accepted)
I guess this was just enough to get accepted without the other two optimizations but I saw it lately (while writing this comment) — http://codeforces.net/contest/86/submission/19784032. However, I decided to keep the first two optimizations because I believe it's good to have them in mind and I don't want to feel like I wasted my time :D
int cmp(const nd& l,const nd& r){
if(l.uu/Block==r.uu/Block){ if (l.uu / Block % 2 == 0) return l.vv < r.vv; else return l.vv > r.vv; } else return l.uu/Block<r.uu/Block;} it takes only 2 second what does it mean? bro
What two seconds are you talking about? It's clear that in this case you need some constant time optimizations, as UnknownNooby said. You have no error, it's just slow.
yes im talking about @Noobgam solution but i can't understand about this condition
if (l.uu / Block % 2 == 0) return l.vv < r.vv;
I have never used and seen that but maybe it speeds up, as we can see from the running time.
yah bro i just minimize division by storing block and use unsigned int it take 1.7 sec only http://codeforces.net/contest/86/submission/19785069 and thanx to u for all of this advice and help
Your code is working so fast because it is incorrect. You can not do
cans += b*(cnt[b]*2 +1);without casting it to long long anywhere.Testset is probably just bad.
b * cnt[b]might overflow so this is undefined behaviour.Mo's is all about constant factor. You can improve it in your case in two ways:
First major fix is fixing add and remove functions. With this simple math you will speed up your solution drastically in some cases. This time the solution barely passes the limit with that.
Second major fix is changing the way how you sort your queries, you can take a look at this example.
Third fix which is minor is that: you should not use long long values to store cnt, this isn't really helping much.
Solution with all three optimisations passes faster than half of time limit: 19784268
Maybe It's TLE because constant of multiplication void add(int b){
} because (a+1)*(a+1)-a*a= 2*a+1;
change to
void add(int b){
cans += (2*cnt[b]+1)*b;
cnt[b]++;
}
So does remove function