fork(1) download
copy 
  1. //longlong5a6
  2. #include <bits/stdc++.h>
  3. #define pii pair<int,int>
  4. #define F first
  5. #define S second
  6. #define bit(i, x)((x >> i) & 1)
  7. #define sobit(i)  __builtin_popcount((int)(i))
  8. #define pb push_back
  9. #define vi vector<int>
  10. #define For(i,x,n) for(int (i)=(int)(x);(i)<=(int)(n);(i)++)
  11. #define round(m,n) setprecision((int)m) << fixed << double(n)
  12. #define down "\n"
  13. #define TASK "near"
  14. #define maxn 200001
  15. #define int long long
  16. #pragma GCC target ("avx2")
  17. #pragma GCC optimization ("O3")
  18. #pragma GCC optimization ("unroll-loops")
  19. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
  20. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  21. using namespace std;
  22.  
  23. int n;
  24. int a[maxn],b[maxn];
  25. struct Knot
  26. {
  27.     int F,S,val;
  28. };
  29. pii line[maxn];
  30. vector<int> C;
  31. int sum;
  32. Knot val[maxn*8];
  33. Knot T[maxn*8];
  34.  
  35. void push(int node)
  36. {
  37.     T[node*2]=T[node*2+1]=val[node];
  38.     val[node*2]=val[node*2+1]=val[node];
  39.     val[node]= {0,0,0};
  40. }
  41. Knot get(int node,int l,int r,int u,int v)
  42. {
  43.     if (v<l|u>r) return {0,0,0};
  44.     if (l>=u&&r<=v) return T[node];
  45.     if (val[node].F) push(node);
  46.     int mid=(l+r)/2;
  47.     Knot Trai=get(node*2,l,mid,u,v);
  48.     Knot Phai=get(node*2+1,mid+1,r,u,v);
  49.     Knot rt=Trai;
  50.     if (Phai.val>Trai.val) rt=Phai;
  51.     return rt;
  52. }
  53. void update(int node,int l,int r,int u,int v,Knot w)
  54. {
  55.     if (r<u||v<l) return;
  56.     if (l>=u&&r<=v)
  57.     {
  58.         T[node]=w;
  59.         val[node]=w;
  60.         return;
  61.     }
  62.     if (val[node].F) push(node);
  63.     int mid=(l+r)/2;
  64.     update(node*2,l,mid,u,v,w);
  65.     update(node*2+1,mid+1,r,u,v,w);
  66.     T[node]=T[node*2];
  67.     if(T[node*2+1].val>T[node*2].val) T[node]=T[node*2+1];
  68. }
  69.  
  70.  
  71. void Init(int node,int l,int r)
  72. {
  73.     T[node]= {0,0,0};
  74.     val[node]= {0,0,0};
  75.  
  76.     if(l==r) return ;
  77.     int mid=(l+r)/2;
  78.     Init(node*2,l,mid);
  79.     Init(node*2+1,mid+1,r);
  80.     //T[node]=min(T[node*2],T[node*2+1]);
  81.  
  82. }
  83.  
  84.  
  85.  
  86. signed main()
  87. {
  88.     ios_base::sync_with_stdio(0);
  89.     cin.tie();
  90.     cout.tie();
  91.     if (fopen("in.txt","r"))
  92.     {
  93.         freopen("in.txt","r",stdin);
  94.  
  95.     }
  96.     if (fopen(TASK".INP","r"))
  97.     {
  98.         freopen(TASK".INP","r",stdin);
  99.         freopen(TASK".OUT","w",stdout);
  100.     }
  101.     int t;
  102.     cin>>t;
  103.     while(t--)
  104.     {
  105.         C.clear();
  106.         sum=0;
  107.         cin>>n;
  108.         For(i,1,n)
  109.         {
  110.             cin>>a[i];
  111.             C.pb(a[i]);
  112.         }
  113.         For(i,1,n)
  114.         {
  115.             cin>>b[i];
  116.             C.pb(b[i]);
  117.         }
  118.         sort(C.begin(),C.end());
  119.         C.resize(unique(C.begin(),C.end())-C.begin());
  120.         For(i,1,n)
  121.         {
  122.             int g=lower_bound(C.begin(),C.end(),a[i])-C.begin()+1;
  123.             int k=lower_bound(C.begin(),C.end(),b[i])-C.begin()+1;
  124.             line[i]= {g,k};
  125.         }
  126.         int res;
  127.         For(i,1,n)
  128.         {
  129.             sum+=a[i]-b[i];
  130.             Knot G=get(1,1,n*2,line[i].S,line[i].S);
  131.             Knot K=get(1,1,n*2,line[i].F,line[i].F);
  132.             int nx=line[i].S;
  133.             int ny=line[i].F;
  134.             if(G.F!=0)
  135.             {
  136.                 if(G.F<line[i].S) nx=G.F;
  137.             }
  138.             if(K.S!=0)
  139.             if(K.S>line[i].F) ny=K.S;
  140.             int ndis=C[ny-1]-C[nx-1];
  141.             update(1,1,n*2,nx,ny, {nx,ny,ndis});
  142.             res=get(1,1,n*2,1,n*2).val;
  143.             cout<<sum-res<<" ";
  144.         }
  145.         Init(1,1,2*n);
  146.         cout<<down;
  147.     }
  148. }
  149.  
Success #stdin #stdout 0s 5600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nUB5hb
language:
C++ (gcc 8.3)
created:
1 day 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!