fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #define ll long long
  7. #define pi 3.14159265358979323846 
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define ar array
  12. #define int long long
  13.  
  14. template<typename T, typename cmp = std::greater<T>>
  15. using pq = priority_queue<T, vector<T>, cmp>;
  16.  
  17. template<typename T, typename cmp = std::less<T>>
  18. using ordered_set = tree<T, __gnu_pbds::null_type, cmp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  19.  
  20. void chay()
  21. {
  22.     ios_base::sync_with_stdio(0);
  23.     cin.tie(0);
  24.     cout.tie(0);
  25.     #define task "Hi"
  26.     freopen(task".INP", "r", stdin);
  27.     freopen(task".OUT", "w", stdout);
  28. }
  29.  
  30. const int N = 2e5, INF = 2e9+7;
  31. const int block = 600;
  32. const long long INFLL = 2e18+7;
  33. long long M = 1e9+7;
  34. int n, cay[N+6], lg, pa[N+5], mx[N+5], tong[N+5], h[N+5];
  35. deque<int> que[N+5];
  36.  
  37. void update(int i, int ss)
  38. {
  39.     for (; i <= n; i += -i&i)
  40.     {
  41.         cay[i] += ss;
  42.     }
  43. }
  44.  
  45. int lay(int i)
  46. {
  47.     int tong = 0;
  48.     for (; i > 0; i -= -i&i)
  49.     {
  50.         tong += cay[i];
  51.     }
  52.     return tong;
  53. }
  54.  
  55. int tim(int e)
  56. {
  57.     int tong = 0, vt = 0;
  58.     for (int i = lg; i >= 0; i--)
  59.     {
  60.         int nw = (1<<i) + vt;
  61.         if (nw <= n && cay[nw] + tong < e)
  62.         {
  63.             tong += cay[nw];
  64.             vt += (1<<i);
  65.         }
  66.     }
  67.     return vt+1;
  68. }
  69.  
  70. int timpa(int u)
  71. {
  72.     if (pa[u] == u) return u;
  73.     return pa[u] = timpa(pa[u]);
  74. }
  75.  
  76. void hoppa(int u, int v)
  77. {
  78.     u = timpa(u);
  79.     v = timpa(v);
  80.  
  81.     int x = mx[u];
  82.     int y = mx[v];
  83.     int kq = tong[u] + tong[v];
  84.     int d = x;
  85.  
  86.  
  87.     //cout<<"--- ";
  88.  
  89.     if (h[x] > h[y])
  90.     {
  91.         //cout<<1<<'\n';
  92.         while (h[que[u].back()] < h[y])
  93.         {
  94.             int cuoi = que[u].back();
  95.             que[u].pop_back();
  96.             int bd = que[u].back()+1;
  97.             kq += (h[y] - h[cuoi]) * (cuoi - bd + 1);
  98.         }
  99.  
  100.         while (h[que[v].front()] != h[y])
  101.         {
  102.             int bd = que[v].front();
  103.             que[v].pop_front();
  104.             int cuoi = que[v].front()-1;
  105.             kq += (h[y] - h[bd]) * (cuoi - bd + 1);
  106.         }
  107.     }
  108.  
  109.     if (h[x] < h[y])
  110.     {
  111.         //cout<<2<<'\n';
  112.         d = y;
  113.         while (h[que[u].back()] != h[x])
  114.         {
  115.             int cuoi = que[u].back();
  116.             que[u].pop_back();
  117.             int bd = que[u].back()+1;
  118.             kq += (h[x] - h[cuoi]) * (cuoi - bd + 1);
  119.         }
  120.  
  121.         while (h[que[v].front()] < h[x])
  122.         {
  123.             int bd = que[v].front();
  124.             que[v].pop_front();
  125.             int cuoi = que[v].front()-1;
  126.             kq += (h[x] - h[bd]) * (cuoi - bd + 1);
  127.         }
  128.     }
  129.  
  130.  
  131.     if (h[x] == h[y])
  132.     {
  133.         while (h[que[u].back()] != h[x])
  134.         {
  135.             int cuoi = que[u].back();
  136.             que[u].pop_back();
  137.             int bd = que[u].back()+1;
  138.             kq += (h[x] - h[cuoi]) * (cuoi - bd + 1);
  139.         }
  140.  
  141.         while (h[que[v].front()] != h[x])
  142.         {
  143.             int bd = que[v].front();
  144.             que[v].pop_front();
  145.             int cuoi = que[v].front()-1;
  146.             kq += (h[x] - h[bd]) * (cuoi - bd + 1);
  147.         }
  148.     }
  149.  
  150.  
  151.     if (que[u].size() < que[v].size())
  152.     {
  153.         while (que[u].size())
  154.         {
  155.             int e = que[u].back();
  156.             que[u].pop_back();
  157.             que[v].push_front(e);
  158.         }
  159.  
  160.         pa[u] = v;
  161.         tong[v] = kq;
  162.         mx[v] = d;
  163.     }
  164.     else
  165.     {
  166.         while (que[v].size())
  167.         {
  168.             int e = que[v].front();
  169.             que[v].pop_front();
  170.             que[u].push_back(e);
  171.         }
  172.  
  173.         pa[v] = u;
  174.         tong[u] = kq;
  175.         mx[u] = d;
  176.     }
  177. }
  178.  
  179. void solve()
  180. {
  181.     cin>>n;
  182.     for (int i = 1; i <= n; i++) 
  183.     {
  184.         cin>>h[i];
  185.     }
  186.     for (int i = 1; i <= n; i++) 
  187.     {
  188.         update(i, 1);
  189.         que[i].push_back(i);
  190.         tong[i] = 0;
  191.         pa[i] = i;
  192.         mx[i] = i;
  193.     }
  194.     lg = log2(n);
  195.     for (int i = 1; i < n; i++)
  196.     {
  197.         int d; cin>>d;
  198.         int bd = tim(d);
  199.         int cuoi = tim(d+1);
  200.         hoppa(bd, cuoi);
  201.         int e = timpa(bd);
  202.         cout<<tong[e]<<'\n';
  203.         update(cuoi, -1);
  204.     }
  205. }
  206.  
  207. signed main ()
  208. {
  209.     ios_base::sync_with_stdio(0);
  210.     cin.tie(0);
  211.     cout.tie(0);
  212.     int t = 1;   
  213.     //cin>>t; 
  214.     while (t--)
  215.     {
  216.         solve();
  217.     }
  218.  
  219.     return 0;
  220. }
Success #stdin #stdout 0.1s 141424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ao1XQ3
language:
C++14 (gcc 8.3)
created:
8 hours 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!