# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1261984 | namhh | Mountains (NOI20_mountains) | C++20 | 357 ms | 26268 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |