Submission #1261984

#TimeUsernameProblemLanguageResultExecution timeMemory
1261984namhhMountains (NOI20_mountains)C++20
100 / 100
357 ms26268 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second const int N = 3e5+5; int n,a[N],bits[N],pre[N]; map<int,int>mp; // ga qua phai chef code huhu :< void update(int u){ while(u <= mp.size()){ bits[u]++; u += u & (-u); } } int get(int u){ int sum = 0; while(u > 0){ sum += bits[u]; u -= u & (-u); } return sum; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; mp[a[i]]++; } int cnt = 0; for(auto it: mp) mp[it.fi] = ++cnt; for(int i = 1; i <= n; i++) a[i] = mp[a[i]]; int ans = 0; for(int i = 1; i <= n; i++){ pre[i] = get(a[i]-1); update(a[i]); } for(int i = 1; i <= mp.size(); i++) bits[i] = 0; for(int i = n; i >= 1; i--){ ans += get(a[i]-1)*pre[i]; update(a[i]); } cout << ans; } // // +.::=. .*: -. // -- :. = -:-- // .= .. .-=++*+++=:. = : // .= ....:=%@@@@@*: . :. // .-+=..: :. .+##%##+. .: .+: // :*@**%* .. :. ::..:.:. --: // .--. +@@@@@%: .==: .###@* // :-- -: -:@@@@# - =@@@@#. .= : + // .: -=--==: == +- :*%*++= .:# // -. .:. . +. -*. =@@. .-. .= // +=.. .. -- .* .#. +@# - :==*= // .=.+=:::: =. =- ##@+ :--+.#@%++%* // .++@@: = + .%%%%@@@@@@@@@@@@@@%. :-@#-: -@. // :@@@@= .+ .= *# .#@.=- =@::-:@: // :-@@%. -- -- :@*. .%# +. - ** :=%. .*@# // :-. .-*-. -: +. %-=::@# .* : - :%- +%.+@+@@ // .- :. **: +: = # : =* =@# -= # #@@@:-@ :*@@. %@ // -=: :: .* .= + # =..@ .*. +. *. *#=.+%@*-%* %@ // :=. :.. .: +. -= .+ # -- #. =- .+ +: =@+ .+-++ @% // ++-=. * -- := # :- +- :* =:+: -@# :@#*%@@@%@+ // *. -- -- := # .= #@#=. +- :=+: :%@-#@@@#@+:@@# // + +. -- := # .= := .+. +*. *@@+=@-=@*-.#@. // = + := .+ # = .= .#.-@. -+ .%# -@@= @# // .= .= .+ + *. = .+.. :*@ == =@. -#@#: @% // .= .= * + =: .=.**: =--: # * *- %* =*=@+#@: // .= := # =. .+ . .= --.#@@@@@#@@@: * -= #..@= **:@@@: // + .= +: -- + # := +@%:@#: -:%= === #..* .#@@%@+.@@+ // * .= .* .= -:-= :- #= ++ =- =@. *: .* -*: : . .@@% // * + * +. :- # -- # *: .@@ %- + =- +-.- :. .@@@. // -: =: := .* +.-- =:-- .*.:.: # .= + *+ - :@%@= // + * *:+. == .+ +. +.# .=-:=- -- -- =+: = -@#%* // + -= *== *. -=-- :+-= ::: =: + %:. = %@+## // .= +: +*- + +:+. +:*. .+ +: #.:. - .+ -@@=#% // -. =. :=#- := =:* .-==#+- +: =- +:-..- :%* =@@:*% // .- +. --+= .**%+-:. -* +-:*:.:. =@@* :-@@ *% // -. += -+== -*#- =- .. .%@#@=.--@* *% // =. .+: :+-*-=+: +%+*@@%%@-= +@- *# // -::= :**=: :@@@@@@%@@- #@ #* // -: +: - .@@#%@@%@@: :@# .#+ // :- :#= -- :@@@#@-=@#. =@- .%= // =:.@@%= =# .+.=. +@@@@* -*: #% :@: // .+ *@@@@@@@@* :@@*@@@* .@+ -@. // .+=%@*%@@@@@#: =@@@%:.: +@: +% // .=%@%#@@@@##@*: =%@@@#: @# ## // :#@%@@@@#@@@@+ :*. @: =@- .@+ // .+@%#%@@:=-.. .=: %*==+. @% -@- // =. =: :-:.:: .-- .= -: =@- - // .- :-. :: .- =-: // .=+-.=-.*- = -..+*: .-:.- = .+*# .... // =. -= -: .. -. +. -. +. -+ -*=: +. // .- +- * -.* #+ .+ =. := // :- --=*: -+ *= -# - -##+-.. .:+#: +. // :- = --=:==+*. =: .: .= =**= = .+ // .= + =-- :- .=. -- .- = // = .- --: .-+*@%*# +. + :- // + +- -:- :*@@@@@@*@#*@@%*=: =: - -. // .* - ::+ =@@@@#-.-@@%%@@+=%@@@%= -:: = :- // .+ :. +-. #@@@= +@@@-#@@%. +@@@+ .:= .- +: // .--. -. :=- :@@+ :@@@@# =@@@# -%@# -= :: :-+- // * - + --. +@@#=%@@@@@. :@@@@% :%@ := =. -=+ // .-**- -. -- .%@@@@+%@+ @@+%@@*-+@@@. :=. - :+*- // :===-==. .-= *@% *@= +%%##=. :=: :. .::-==-. // .::-=+=+=-:. #%: -#: .-*#+===-:. // ..::---====---::.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...