fork download
copy 
  1. // ~~ icebear love attttttt ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 2e5 + 5;
  38. int n, h[N], c[N];
  39. vector<int> compress;
  40.  
  41. template<class T>
  42.     struct FenwickTree {
  43.         T ft[N];
  44.         void reset() {
  45.             FOR(i, 1, N - 5) ft[i] = 0;
  46.         }
  47.  
  48.         void update(int x, T val) {
  49.             for(; x < N; x += x & -x) ft[x] += val;
  50.         }
  51.  
  52.         T get(int x) {
  53.             T ans = 0;
  54.             for(; x; x -= x & -x) ans += ft[x];
  55.             return ans;
  56.         }
  57.  
  58.         int search(int v) {
  59.             int sum = 0, pos = 0;
  60.             RED(i, 18)
  61.                 if (pos + MASK(i) < N && sum + ft[pos + MASK(i)] < v) {
  62.                     pos += MASK(i);
  63.                     sum += ft[pos];
  64.                 }
  65.             return pos + 1;
  66.         }
  67.     };
  68.  
  69. FenwickTree<int> ftPos;
  70. FenwickTree<__int128> ftC, ftCH;
  71. __int128 sumC, sumCH;
  72.  
  73. void print(__int128 x) {
  74.     vector<int> digit;
  75.     if (x == 0) digit.pb(0);
  76.     while(x) {
  77.         digit.pb(x % 10);
  78.         x /= 10;
  79.     }
  80.     while(!digit.empty()) cout << digit.back(), digit.pop_back();
  81. }
  82.  
  83. __int128 f(int p) {
  84.     int pos = ftPos.search(p);
  85.     int height = compress[pos - 1];
  86.     // cout << p << ' ' << height << endl;
  87.     // print(ftC.get(pos)); cout << endl;
  88.     // print(ftCH.get(pos)); cout << endl;
  89.     __int128 res = ftC.get(pos) * height * 2 - sumC * height - ftCH.get(pos) * 2 + sumCH;
  90.     return res;
  91. }
  92.  
  93. void init(void) {
  94.     cin >> n;
  95.     FOR(i, 1, n) cin >> h[i], compress.pb(h[i]);
  96.     FOR(i, 1, n) cin >> c[i];
  97.     sort(all(compress));
  98.     compress.resize(unique(all(compress)) - compress.begin());
  99.     FOR(i, 1, n) h[i] = lower_bound(all(compress), h[i]) - compress.begin() + 1;
  100. }
  101.  
  102. void process(void) {
  103.     __int128 MAX = 1;
  104.     FOR(i, 1, 100) MAX *= 2;
  105.     ll tmp;
  106.     FOR(i, 1, n) {
  107.         tmp = 1LL * c[i] * compress[h[i] - 1];
  108.         sumC += c[i];
  109.         sumCH += tmp;
  110.         ftC.update(h[i], c[i]);
  111.         ftCH.update(h[i], tmp);
  112.         ftPos.update(h[i], +1);
  113.         int l = 1, r = i;
  114.         while(r - l > 2) {
  115.             int m1 = l + (r - l) / 3;
  116.             int m2 = r - (r - l) / 3;
  117.             if (f(m1) < f(m2)) r = m2;
  118.             else l = m1;
  119.         }
  120.         __int128 res = MAX;
  121.         FOR(j, l, r) minimize(res, f(j));
  122.         print(res); cout << ' ';
  123.     }
  124. }
  125.  
  126. int main() {
  127.     ios_base::sync_with_stdio(0);
  128.     cin.tie(0); cout.tie(0);
  129.     if (fopen(task".inp", "r")) {
  130.         freopen(task".inp", "r", stdin);
  131.         freopen(task".out", "w", stdout);
  132.     }
  133.     int tc = 1;
  134. //    cin >> tc;
  135.     while(tc--) {
  136.         init();
  137.         process();
  138.     }
  139.     return 0;
  140. }
Success #stdin #stdout 0.01s 5624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nu0Vvd
language:
C++ (gcc 8.3)
created:
12 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!