Submission #1229280

#TimeUsernameProblemLanguageResultExecution timeMemory
1229280nai0610medians (balkan11_medians)C++20
0 / 100
61 ms12352 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; int n,a[100009],b[200009]; set<int> num; void update(int i,int v) { while(i<2*n) { b[i]+=v; i+=(i&-i); } } int get(int i) { int r=0; while(i>0) { r+=b[i]; i-=(i&-i); } return r; } int main() { if(fopen("D:/CPP/THEMIS/test.inp","r")) { freopen("D:/CPP/THEMIS/test.inp","r",stdin); freopen("D:/CPP/THEMIS/test.out","w",stdout); } ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;++i) cin>>a[i]; for(int i=1;i<2*n;++i) num.insert(i); update(a[1],1); cout<<a[1]<<" "; num.erase(a[1]); for(int i=2;i<=n;++i) { int l=get(a[i]-1),e,r; e=get(a[i])-l; r=2*i-e-l-3; auto it=num.begin(); while(!num.empty() and l<i-1) { cout<<*it<<" "; update(*it,1); ++l; it=num.erase(it); } if(e==0) { cout<<a[i]<<" "; update(a[i],1); num.erase(a[i]); } it=prev(num.end()); while(!num.empty() and r<i-1) { cout<<*it<<" "; update(*it,1); ++r; it=--num.erase(it); } } } /* ........................ ..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::.. ..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+. ..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:. ..:-+*%@@@@@@@%%%##########################################%@@@@+:. ..:=+%@@@@@@%%#####################################################@@@@+.. ....-+%@@@@@@%#############################################################@@@@=.. ..=#@@@@@%%###################################################################%@@@%-. .:+#%@@@@%%#########################################################################%@@@#:. .:=*%@@@%%###############################################################################%@@@@-. ..-*%@@@%%#####################################################################################%@@@=. ..+@@@@###########################################################################################%@@@*.. .*@@@#*##############################################################################################@@@%. .+@@@#**################################################################################################@@@%:. .-%@@#**####%##############################################################################################%@@%:. .+@@#***###%%################################################################################################%@@@-. :#@%****###%%*#################################################################################################%@@@-. -@@%****###@%*###################################################################################################%@@@-. -@@#***###%@#*#####################################################################################################%@@@=. -@@#***###@@#*#######################################################################################################@@@%-. :@@#***###@%**#########################################################################################################@@@+. :%@#***##%@%**##########################################################################################################%@@@. .#@%***##%@%**############################################################################################################%@@*. .+@%***##@@#**##############################################################################################@@##############@@@:. :@@***##@@#**###############################################################################################@@@%############%@@#. .%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=. .*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%. -@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=. .#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%. =@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=. .@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%. .#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@- ..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#. .-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:. ...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*. ..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@. .#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+. :#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%. .+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-. .+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#. .:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:. .....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*. .=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@. .%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=. .+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%. .@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=. .+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%. :@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+. .*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:. :@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#. .*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*. .=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=. -@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=. .+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=. .-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+. ..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#. ...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-. .-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*.. -@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=. .:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+. .+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:. .:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+. .+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+. .#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=. .-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-. ..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:. .=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=.. .=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-. .=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+.. .-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:. ..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+.. .:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:. ..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-. .:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=.. .-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=.. ...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-.. ...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:.. ..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=.. ..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:.. ..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-. ..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-.. .....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:... ..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:.. ...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:.. ...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:.. ...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:.. .*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:.. .@@%****##########@#====%%###@##@%%%@@@%-:.... -@@#****##########@#===+@#***@%=@%###@@%. =@@*****##########%@===#@#***%@=%@###%@@- .*@@*****###########@*==*%%%%%@@+@%###%@@+. .@@%****############%@+=====++==%@#####@@%. =@@#****#############@@========#@######@@@. .*@@*****############@@%@+=====*@#######@@@=. .%@@*****###########%@##@@#===#@########%@@*. -@@%****###########%@%##@%%%*#@##########@@%. =@@#****###########@%###@##%@@###########@@@-. +@@*****##########@@###%@##%@@###########@@@+. .%@@****##########@@####@%##%@@###########%@@%. -@@%****#########@@#####@###%@@############@@@: =@@#****########%@#####%@####@@############@@@=. #@@*****#######%@######@%####@@############%@@#. .%@@****#######%@######%@#####@@############%@@%. -@@%****######%@#######%@#####@@%############@@@-. =@@#****#####%@########@%#####@@%############@@@+. +@@#****####%@########%@######@@%############%@@#. .%@@****####%@#########@@######@@%############%@@@: :@@%****###%@##########@%######@@%#############@@@=. =@@%****##%%##########%@#######@@%#############@@@*. #@@#****#%%###########@@#######@@@#############%@@%. .%@@*****%############%@%#######@@@#############%@@@: -@@@****##############@@########%@@##############@@@+. -@@%****##############@%########%@@##############@@@#. .*@@#****#############@@#########%@@##############%@@@: .%@@*****#############@%#########%@@##############%@@@-. :@@@*****############%@##########%@@###############@@@*. -@@%*****############@%##########%@@###############@@@%. #@@#****############%@############@@###############%@@@: .%@@#****############@%############@@%###############@@@=. :@@@*****###########%@#############@@%###############@@@*. -@@%*****###########@%#############@@%###############@@@%. =@@%*****##########%@##############@@%###############%@@@: .#@@#*****##########@%##############@@%################@@@+. :@@@*****###########@###############@@%################@@@#. */

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen("D:/CPP/THEMIS/test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
medians.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("D:/CPP/THEMIS/test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...