fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define maxn 300005
  4. #define pii pair <int, int>
  5. #define fi first
  6. #define se second
  7. #define MOD 1022071997
  8. #define int long long
  9.  
  10. using namespace std;
  11.  
  12. int n,par[maxn];
  13. int a[maxn],b[maxn];
  14. int cost[maxn],K;
  15. int order[maxn],L[maxn],R[maxn];
  16. int ans[maxn];
  17.  
  18. bool cmp(int x,int y){
  19.    return cost[x] < cost[y];
  20. }
  21.  
  22. int find_par(int u){
  23.    return (u==par[u] ? u : par[u]=find_par(par[u]));
  24. }
  25.  
  26.  
  27. signed main()
  28. {
  29.     ios_base::sync_with_stdio(0);
  30.     cin.tie(0);cout.tie(0);
  31.     cin>>n>>K;
  32.     for(int i=1;i<=n;i++) cin>>a[i];
  33.     for(int i=1;i<=n;i++) cin>>b[i];
  34.     for(int i=1;i<=n;i++){
  35.         if(b[i] > a[i]) cost[i]=b[i]-a[i];
  36.         else cost[i]=b[i]+K+1-a[i];
  37.         cout<<cost[i]<<' ';
  38.         par[i]=i;
  39.         R[i]=cost[i]; L[i]=cost[i];
  40.         ans[i]=cost[i];
  41.     }
  42.     cout<<'\n';
  43.     for(int i=1;i<=n;i++) order[i]=i;
  44.     sort(order+1,order+n+1,cmp);
  45.     for(int i=1;i<=n;i++){
  46.         int pos=order[i];
  47.         if(pos>1){
  48.             int pre=find_par(pos-1);
  49.             cout<<pos<<' '<<pre<<' '<<R[pre]<<'\n';
  50.             if(R[pre] < cost[pos]){
  51.                 ans[pre]+=cost[pos]-R[pre];
  52.             }
  53.             else R[pre]=cost[pos];
  54.             par[pos]=pre;
  55.         }
  56.         if(pos+1<=n){
  57.             int nxt=find_par(pos+1);
  58.             if(L[nxt] < cost[pos]){
  59.                 ans[nxt]+=cost[pos]-L[nxt];
  60.             }
  61.             else L[nxt]=cost[pos];
  62.             par[pos]=nxt;
  63.         }
  64.     }
  65.     int sum=0;
  66.     for(int i=1;i<=n;i++) {
  67.         if(find_par(i)==par[i]) {
  68.             sum+=ans[i];
  69.             //cout<<ans[i]<<' ';
  70.         }
  71.     }
  72.     cout<<sum;
  73.     return 0;
  74. }
  75.  
  76.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/8h54zT
language:
C++14 (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!