fork download
copy 
  1. /* Authors: Vu Hoang Bach from Phuoc Hoa Secondary School */
  2. /* Enjoy TheFatRat's music while reading my code. Link: https://w...content-available-to-author-only...e.com/watch?v=GCx9FU59FJc&t=669s */
  3.  
  4. //#pragma GCC optimize("O3", "unroll-loops")
  5. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  6.  
  7. #include <bits/stdc++.h>
  8. #define ldb long double
  9. //#define double ldb
  10. #define db double
  11. #define name "test"
  12. #define unomap unordered_map
  13. #define unoset unordered_set
  14. #define endl '\n'
  15. #define str string
  16. #define strstr stringstream
  17. #define sz(a) a.size()
  18. #define ll long long
  19. //#define int ll
  20. #define pii pair <int, int>
  21. #define pll pair <ll, ll>
  22. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  23. #define ull unsigned ll
  24. #define fir first
  25. #define sec second
  26. #define idc cin.ignore()
  27. #define lb lower_bound
  28. #define ub upper_bound
  29. #define all(s) s.begin(), s.end()
  30. #define rev reverse
  31. #define sigma ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  32. #define skibidi int main
  33. #define rizz signed main
  34. #define gcd __gcd
  35. #define found(a, mp) mp.find(a) != mp.end()
  36. #define game_over exit(0);
  37. #define stfu return 0;
  38. #define stop break;
  39. #define odd(n) n & 1
  40. #define pushb push_back
  41. #define popb pop_back
  42. #define pushf push_front
  43. #define popf pop_front
  44. #define even(n) !odd(n)
  45. #define mul2x(a, x) a << x
  46. #define div2x(a, x) a >> x
  47. #define no_check continue;
  48. #define lcm(a, b) a / __gcd(a, b) * b
  49. #define log_base(x, base) log(x) / log(base)
  50. #define debug clog << "No errors!"; game_over;
  51. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  52. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  53. #define fors(i, a, b) for (int i = a; i >= b; --i)
  54. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  55. #define meme memset
  56. #define pqueue priority_queue
  57. #define want_digit(x) cout << fixed << setprecision(x);
  58. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  59. using namespace std;
  60. const int MOD = 1e9 + 7; // 998244353
  61. const int inf = 1e9;
  62. const ll INF = 1e18;
  63. const int N = 2e5;
  64.  
  65. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  66. ll random(const ll &L, const ll &R)
  67. {
  68.     return uniform_int_distribution<ll> (L, R) (rng);
  69. }
  70.  
  71. int n, k, a[N + 5];
  72. multiset <int> ms;
  73.  
  74. vector <ll> comp;
  75.  
  76. int calc_comp(const ll &x)
  77. {
  78.     return lb(all(comp), x) - comp.begin() + 1;
  79. }
  80.  
  81. void compress()
  82. {
  83.     forw (i, 1, n) comp.pushb(a[i]);
  84.     sort(all(comp));
  85.     Unique(comp);
  86.     forw (i, 1, n)
  87.         a[i] = calc_comp(a[i]);
  88. }
  89.  
  90. pair <int, ll> add(const pair <int, ll> &x, const pair <int, ll> &y)
  91. {
  92.     pair <int, ll> res = {x.fir + y.fir, x.sec + y.sec};
  93.     return res;
  94. }
  95.  
  96. pair <int, ll> tree[N * 4 + 5];
  97. void update(int id, int l, int r, int pos, int val)
  98. {
  99.     if (l > pos || pos > r) return;
  100.     if (l == r)
  101.     {
  102.         tree[id].fir += val;
  103.         tree[id].sec = (ll) tree[id].fir * (ll) comp[pos - 1];
  104.         return;
  105.     }
  106.  
  107.     int mid = (l + r) / 2;
  108.     update(id * 2, l, mid, pos, val);
  109.     update(id * 2 + 1, mid + 1, r, pos, val);
  110.     tree[id] = add(tree[id * 2], tree[id * 2 + 1]);
  111. }
  112.  
  113. pair <int, ll> get(int id, int l, int r, int sta, int fin)
  114. {
  115.     if (l > fin || sta > r) return pii(0, 0);
  116.     if (sta <= l && r <= fin) return tree[id];
  117.  
  118.     int mid = (l + r) / 2;
  119.     return add(get(id * 2, l, mid, sta, fin), get(id * 2 + 1, mid + 1, r, sta, fin));
  120. }
  121.  
  122. int calc_med()
  123. {
  124.     multiset <int>::iterator it = ms.begin();
  125.     forw (j, 1, (k + 1) / 2 - 1) ++it;
  126.     int med = *it;
  127.     return med;
  128. }
  129.  
  130. ll calc(int med)
  131. {
  132.     int compressed_med = calc_comp(med);
  133.     pair <int, ll> lower = get(1, 1, n, 1, compressed_med - 1), upper = get(1, 1, n, compressed_med + 1, n);
  134.     ll res = (ll) med * (ll) lower.fir - lower.sec;
  135.     res += upper.sec - (ll) med * (ll) upper.fir;
  136.     return res;
  137. }
  138.  
  139. void print(multiset <int> se)
  140. {
  141.     while (!se.empty())
  142.     {
  143.         cout << *se.begin() << ' ';
  144.         se.erase(se.begin());
  145.     }
  146.     cout << endl;
  147. }
  148.  
  149. void cook()
  150. {
  151.     cin >> n >> k;
  152.     forw (i, 1, n) cin >> a[i];
  153.     compress();
  154.  
  155.     meme(tree, 0, sizeof(tree));
  156.  
  157.     forw (i, 1, k)
  158.     {
  159.         ms.insert(comp[a[i] - 1]);
  160.         update(1, 1, n, a[i], 1);
  161.     }
  162.  
  163. //    print(ms);
  164.  
  165.     cout << calc(calc_med()) << ' ';
  166.  
  167.     forw (i, k + 1, n)
  168.     {
  169.         ms.erase(ms.find(comp[a[i - k] - 1]));
  170.         update(1, 1, n, a[i - k], -1);
  171.  
  172.         ms.insert(comp[a[i] - 1]);
  173.         update(1, 1, n, a[i], 1);
  174.  
  175. //        print(ms);
  176.  
  177.         cout << calc(calc_med()) << ' ';
  178.     }
  179.     cout << endl;
  180. }
  181.  
  182. /*
  183. 10 5
  184. 4 6 10 4 3 8 8 10 8 9
  185. */
  186.  
  187. skibidi()
  188. //rizz()
  189. {
  190.     srand(time(NULL));
  191.     sigma;
  192.     /*
  193.     if (fopen(name".INP", "r"))
  194.     {
  195.         freopen(name".INP", "r", stdin);
  196.         freopen(name".OUT", "w", stdout);
  197.     }
  198.     */
  199.     int numTest = 1;
  200. //    cin >> numTest;
  201.     while (numTest--)
  202.     {
  203.         cook();
  204.     }
  205.     stfu;
  206. }
Success #stdin #stdout 0.01s 16128KB
comments (?)
stdin
copy 
10 5
4 6 10 4 3 8 8 10 8 9
stdout
copy 
9 11 11 11 7 3
https://ideone.com/Tz0QXW
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!