SHARE
TWEET

Untitled

a guest Sep 30th, 2017 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  6. #define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
  7. #define ll long long
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define eb emplace_back
  13. #define pii pair<ll , ll>
  14. #define pll pair<long long ,long long >
  15. #define sd(x) scanf("%d",&x)
  16. #define sld(x) scanf("%lld",&x)
  17. #define pd(x) prllf("%d\n",x)
  18. #define pld(x) prllf("%lld\n",x)
  19. #define pss prllf
  20. #define mod 1000000007
  21. #define INF 1e18
  22. #define eps 0.00001
  23. #define debug(n1) cout<<n1<<endl
  24.  
  25. const ll N = 3e5 + 5;
  26. const ll M = 320;
  27. ll n;
  28. ll m;
  29. pll a[N];
  30. pll tree1[4 * N];
  31. pll tree2[4 * N];
  32. ll ind1[4 * N];
  33. ll ind2[4 * N];
  34. set < ll > store[4 * N];
  35.  
  36. void build_max(pll tree[] , ll A[] , ll node , ll s , ll e) {
  37.     if(s == e) {
  38.         tree[node].fi = A[s];
  39.         tree[node].se = s;
  40.         ind2[s] = node;
  41.         return ;
  42.     }
  43.     ll mid = (s + e) / 2;
  44.     build_max(tree , A , 2 * node + 1 , s , mid);
  45.     build_max(tree , A , 2 * node + 2 , mid + 1 , e);
  46.     if(tree[2 * node + 1].fi > tree[2 * node + 2].fi) {
  47.         tree[node].fi = tree[2 * node + 1].fi;
  48.         tree[node].se = tree[2 * node + 1].se;
  49.     }
  50.     else{
  51.         tree[node].fi = tree[2 * node + 2].fi;
  52.         tree[node].se = tree[2 * node + 2].se;
  53.     }
  54.     return ;
  55. }
  56. pll query_max(pll tree[] , ll node , ll s , ll e , ll l , ll r) {
  57.     if(l > e || r < s) {
  58.         return make_pair(LLONG_MIN , -1);
  59.     }
  60.     if(l <= s && r >= e) {
  61.         return tree[node];
  62.     }
  63.     ll mid = (s + e) / 2;
  64.     pll li = query_max(tree , 2 * node + 1 , s , mid , l , r);
  65.     pll re = query_max(tree , 2 * node + 2 , mid + 1 , e , l , r);
  66.     if(li.fi > re.fi) {
  67.         return li;
  68.     }
  69.     else{
  70.         return re;
  71.     }
  72. }
  73.  
  74. void build_min(pll tree[] , ll A[] , ll node , ll s , ll e) {
  75.     if(s == e) {
  76.         tree[node].fi = A[s];
  77.         tree[node].se = s;
  78.         ind1[s] = node;
  79.         return ;
  80.     }
  81.     ll mid = (s + e) / 2;
  82.     build_min(tree , A , 2 * node + 1 , s , mid);
  83.     build_min(tree , A , 2 * node + 2 , mid + 1 , e);
  84.     if(tree[2 * node + 1].fi < tree[2 * node + 2].fi) {
  85.         tree[node].fi = tree[2 * node + 1].fi;
  86.         tree[node].se = tree[2 * node + 1].se;
  87.     }
  88.     else{
  89.         tree[node].fi = tree[2 * node + 2].fi;
  90.         tree[node].se = tree[2 * node + 2].se;
  91.     }
  92.     return ;
  93. }
  94. pll query_min(pll tree[] , ll node , ll s , ll e , ll l , ll r) {
  95.     if(l > e || r < s) {
  96.         return make_pair(LLONG_MAX , -1);
  97.     }
  98.     if(l <= s && r >= e) {
  99.         return tree[node];
  100.     }
  101.     ll mid = (s + e) / 2;
  102.     pll li = query_min(tree , 2 * node + 1 , s , mid , l , r);
  103.     pll re = query_min(tree , 2 * node + 2 , mid + 1 , e , l , r);
  104.     if(li.fi < re.fi) {
  105.         return li;
  106.     }
  107.     else{
  108.         return re;
  109.     }
  110. }
  111.  
  112. void update_max(pll tree[] , ll node, ll b, ll e, ll idx, ll val)
  113. {
  114.  if (b>e || b>idx || e<idx ) return;
  115.  if (node == ind2[idx]) //at leaf node
  116.  {
  117.   tree[node].fi = val;
  118.   tree[node].se = -1;
  119.   return;
  120.  }
  121.  
  122.  update_max( tree , node*2 + 1 , b , (b+e)/2 , idx, val );
  123.  update_max( tree , node*2 + 2 , (b+e)/2 + 1 , e , idx, val );
  124.  
  125.  if(tree[2 * node + 1].fi > tree[2 * node + 2].fi) {
  126.         tree[node].fi = tree[2 * node + 1].fi;
  127.         tree[node].se = tree[2 * node + 1].se;
  128.     }
  129.     else{
  130.         tree[node].fi = tree[2 * node + 2].fi;
  131.         tree[node].se = tree[2 * node + 2].se;
  132.     }
  133.     return ;
  134.  
  135. }
  136.  
  137. void update_min(pll tree[] , ll node, ll b, ll e, ll idx, ll val)
  138. {
  139.  if (b>e || b>idx || e<idx ) return;
  140.  if (node == ind1[idx])
  141.  {
  142.   tree[node].fi = val;
  143.   tree[node].se = -1;
  144.   return;
  145.  }
  146.  
  147.  update_min( tree , node*2 + 1 , b , (b+e)/2 , idx, val );
  148.  update_min( tree , node*2 + 2 , (b+e)/2 + 1 , e , idx, val );
  149.  
  150.  //now some change might have been made in either of the child nodes.
  151.  if(tree[2 * node + 1].fi < tree[2 * node + 2].fi) {
  152.         tree[node].fi = tree[2 * node + 1].fi;
  153.         tree[node].se = tree[2 * node + 1].se;
  154.     }
  155.     else{
  156.         tree[node].fi = tree[2 * node + 2].fi;
  157.         tree[node].se = tree[2 * node + 2].se;
  158.     }
  159.     return ;
  160.  
  161. }
  162.  
  163. ll ai[N];
  164. int main() {
  165.     sld(n);
  166.     for(ll i = 1 ; i <= n ; i++) {
  167.         sld(a[i].fi);
  168.         a[i].se = i;
  169.         ai[i] = a[i].fi;
  170.         store[a[i].fi].insert(i);
  171.     }
  172.     build_min(tree1 , ai , 1 , 1 , n);
  173.     build_max(tree2 , ai , 1 , 1 , n);
  174.     sort(a + 1 , a + n + 1);
  175.  
  176.     ll res = 0;
  177.     for(ll i = 1 ; i <= n ; i++) {
  178.         pll ans1 = a[i];
  179.         pll ans2 = query_max(tree2 , 1 , 1 , n , ans1.se + 1LL , n);
  180.         if(ans2.fi > 4 * N) continue;
  181.         if(store[ans2.fi].size() > 0)
  182.         {
  183.             if(store[ans2.fi].upper_bound(ans1.se) != store[ans2.fi].end())
  184.             ans2.se = (*store[ans2.fi].upper_bound(ans1.se));
  185.         }
  186.      //   cout << ans1.fi << " " << ans2.fi << endl;
  187.        
  188.         if(ans1.fi < ans2.fi && ans1.se < ans2.se) {
  189.             res += ans2.fi - ans1.fi;
  190.            // cout << ans1.se << " ff " << ans2.se << endl;
  191.             update_min(tree1 , 1 , 1 , n , ans1.se , LLONG_MAX);
  192.             update_max(tree2 , 1 , 1 , n , ans2.se , LLONG_MIN);
  193.             store[ans2.fi].erase(ans2.se);
  194.         }
  195.     }
  196.  
  197.     cout << res << endl;
  198.  
  199.     return 0;
  200. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top