Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
#include
#include
#include
using namespace std; const int maxn = 2e5 + 10; multiset
smaller_values, greater_values; int k; void insert_value(int x) { int max_in_smaller = *smaller_values.rbegin(); if(max_in_smaller < x) { greater_values.insert(x); if(greater_values.size() > k / 2) { int min_in_greater = *greater_values.begin(); smaller_values.insert(min_in_greater); greater_values.erase(greater_values.find(min_in_greater)); } } else { smaller_values.insert(x); if(smaller_values.size() > (k + 1) / 2) { int tmp_max_in_smaller = *smaller_values.rbegin(); greater_values.insert(tmp_max_in_smaller); smaller_values.erase(smaller_values.find(tmp_max_in_smaller)); } } } void remove_value(int x) { if(greater_values.find(x) != greater_values.end()) { greater_values.erase(greater_values.find(x)); } else if(smaller_values.find(x) != smaller_values.end()) { smaller_values.erase(smaller_values.find(x)); } if(smaller_values.empty()) { smaller_values.insert(*greater_values.begin()); greater_values.erase(greater_values.begin()); } } int main() { ios_base::sync_with_stdio(false); int n; cin >> n >> k; vector
v(n); for(int i = 0; i < n; i++) { cin >> v[i]; } smaller_values.insert(v[0]); for(int i = 1; i < k; i++) { insert_value(v[i]); } cout << *smaller_values.rbegin() << " "; for(int i = k; i < n; i++) { if(k > 1) { remove_value(v[i - k]); insert_value(v[i]); } else { insert_value(v[i]); remove_value(v[i - 1]); } cout << *smaller_values.rbegin() << " "; } return 0; } // 5, 1, 2, 3 // 1, 2, 3, 5
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)