№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | -is-this-fft- | 161 |
3 | maomao90 | 159 |
3 | atcoder_official | 159 |
5 | cry | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
Название |
---|
when there are large input or output put these 2 lines at the start of your main : ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
they will fast input output , also use '\n' or "\n" instead of endl
cout.tie(0)
does nothing. Onlycin.tie(0)
is necessary.so after u do these two optimization , still TLE (time limit .... )
what u do that u take each value from a or b and count the mx subarray in a , b : so for 2*n values u iterate over a , b so your time complexity( search about it if u don't know it) is O ( n * n ) which is large enough to get TLE
but what if we preprocess the mxa[elemnt] >> max subarray that contains only elemnt , mxb[elemnt] so you won'y need the functions that takes n instruction to answer fn(a,ele) , fn(b,ele)
so know we need to think how to build mxa[ele] ... don't read this untill u try to find out how >> u can iterate over a one time with cnt = 0 : a[i]!=a[i-1] >> cnt=1 >> u start a new subarray a[i]==a[i-1] >> cnt++ mxa[a[i]] = max(mxa[a[i]] , cnt) >> u don't need to wait untill subarray is closed
https://codeforces.net/contest/1831/submission/262226998
thanks