fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. void solve() {
  7.     int n;
  8.     if (!(cin >> n)) return;
  9.  
  10.     multiset<ll> ms;
  11.     // Iterators to mark boundaries
  12.     // L points to the first element of Muhammad's share
  13.     // R points to the first element of Shehab's share
  14.     auto L = ms.end();
  15.     auto R = ms.end();
  16.  
  17.     ll ahmed_sum = 0, muhammad_sum = 0, shehab_sum = 0;
  18.  
  19.     for (int i = 1; i <= n; i++) {
  20.         ll val;
  21.         cin >> val;
  22.  
  23.         // Step 1: Insert the new element and initially assign its sum
  24.         auto it = ms.insert(val);
  25.  
  26.         if (ms.size() == 1) {
  27.             L = it;
  28.             R = ms.end();
  29.             muhammad_sum += val;
  30.             cout << ahmed_sum << " " << muhammad_sum << " " << shehab_sum << "\n";
  31.             continue;
  32.         }
  33.  
  34.         // Figure out where it was inserted relative to our pointers
  35.         if (L != ms.end() && val < *L) {
  36.             ahmed_sum += val;
  37.         } else if (R != ms.end() && val >= *R) {
  38.             shehab_sum += val;
  39.         } else {
  40.             muhammad_sum += val;
  41.         }
  42.  
  43.         // Target sizes for this day
  44.         ll M = i;
  45.         ll target_ahmed = M / 2;
  46.         ll target_shehab = (M - target_ahmed) / 2;
  47.         ll target_muhammad = M - target_ahmed - target_shehab;
  48.  
  49.         // Current sizes can be implicitly tracked by moving L and R until targets match
  50.         // We look at how many elements should be before L (Ahmed's count)
  51.         // Since we only added ONE element, the pointers will shift by at most 1 position.
  52.  
  53.         // Fix Ahmed's boundary (L)
  54.         // We can use a distance trick or just trace the math. 
  55.         // Instead of heavy distance calculations, we track counts explicitly:
  56.         static ll curr_ahmed_cnt = 0;
  57.         static ll curr_shehab_cnt = 0;
  58.  
  59.         if (val < *L) curr_ahmed_cnt++;
  60.         else if (R != ms.end() && val >= *R) curr_shehab_cnt++;
  61.  
  62.         // Adjust L pointer
  63.         while (curr_ahmed_cnt < target_ahmed) {
  64.             // L moves right, element at L goes from Muhammad to Ahmed
  65.             ahmed_sum += *L;
  66.             muhammad_sum -= *L;
  67.             L++;
  68.             curr_ahmed_cnt++;
  69.         }
  70.         while (curr_ahmed_cnt > target_ahmed) {
  71.             // L moves left, element before L goes from Ahmed to Muhammad
  72.             L--;
  73.             ahmed_sum -= *L;
  74.             muhammad_sum += *L;
  75.             curr_ahmed_cnt--;
  76.         }
  77.  
  78.         // Adjust R pointer
  79.         while (curr_shehab_cnt < target_shehab) {
  80.             // R moves left, element before R goes from Muhammad to Shehab
  81.             R--;
  82.             shehab_sum += *R;
  83.             muhammad_sum -= *R;
  84.             curr_shehab_cnt++;
  85.         }
  86.         while (curr_shehab_cnt > target_shehab) {
  87.             // R moves right, element at R goes from Shehab to Muhammad
  88.             muhammad_sum += *R;
  89.             shehab_sum -= *R;
  90.             R++;
  91.             curr_shehab_cnt--;
  92.         }
  93.  
  94.         cout << ahmed_sum << " " << muhammad_sum << " " << shehab_sum << "\n";
  95.     }
  96. }
  97.  
  98. int main() {
  99.     ios_base::sync_with_stdio(false);
  100.     cin.tie(NULL);
  101.     solve();
  102.     return 0;
  103. }
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rREueB
language:
C++ (gcc 8.3)
created:
2 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!