Advertisement
Guest User

Untitled

a guest
Apr 8th, 2021
340
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. using namespace std;
  5. // using namespace __gnu_pbds;
  6. #define mod 1000000007
  7. #define rep(i, n) for(int i = 0; i < n; i++)
  8. #define rep1(i,a,b) for(int i=a;i<b;i++)
  9. #define endl "\n"
  10. #define PI 3.14159265358979323846  /* pi */
  11. #define is_pot(n) (n&& !(n&(n-1)))
  12. #define all(v)  ((v).begin()),((v).end())
  13. #define degreesToRadians(angleDegrees) (angleDegrees * PI / 180.0) // Converts degrees to radians.
  14. #define radiansToDegrees(angleRadians) (angleRadians * 180.0 / PI) // Converts radians to degrees.
  15. #define int long long
  16. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
  17. #define epsilon 1e-9
  18. typedef long long ll;
  19. typedef long double ld;
  20. // template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
  21.  
  22. int dx[]={1, 0, -1, 0};
  23. int dy[]={0, 1, 0, -1};
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40. const int N=4e5+5;
  41. int tree[2*N], sz, fre[N];
  42.  
  43. void init(int n)
  44. {
  45.     sz=1;
  46.     while(sz<n)
  47.         sz*=2;
  48. }
  49.  
  50. void update(int i, int v, int node, int lx, int rx)
  51. {
  52.     if(rx-lx==1)
  53.     {
  54.         tree[node]=v;
  55.         return;
  56.     }
  57.     int mid=(lx+rx)/2;
  58.     if(i<mid)
  59.         update(i, v, 2*node+1, lx, mid);
  60.     else
  61.         update(i, v, 2*node+2, mid, rx);
  62.     tree[node]=tree[2*node+1]+tree[2*node+2];
  63. }
  64.  
  65. int query(int l, int r, int node, int lx, int rx)
  66. {
  67.     if(lx>=r || rx<=l)
  68.         return 0;
  69.     if(lx>=l && rx<=r)
  70.         return tree[node];
  71.     int mid=(lx+rx)/2;
  72.     return query(l, r, 2*node+1, lx, mid)+query(l, r, 2*node+2, mid, rx);
  73. }
  74.  
  75. void solve()
  76. {
  77.     int n;
  78.     cin>>n;
  79.  
  80.     n*=2;
  81.  
  82.     init(n);
  83.  
  84.     vector<int> ans(n/2+1), dis(n/2+1, 0);
  85.  
  86.     for(int i=0;i<n;i++)
  87.     {
  88.         int x;
  89.         cin>>x;
  90.         if(!fre[x])
  91.             fre[x]=i+1;
  92.         else
  93.         {
  94.             dis[x]=i-fre[x];
  95.             int l=fre[x]-1;
  96.             int r=i+1;
  97.             ans[x]=query(l, r, 0, 0, sz);
  98.             update(l, 1, 0, 0, sz);
  99.         }
  100.     }
  101.     for(int i=1;i<=n/2;i++)
  102.         cout<<dis[i]-2*ans[i]<<" ";
  103. }
  104.  
  105. signed main() {
  106.  
  107.     fastio
  108.  
  109.         // int t;cin>>t;while(t--)
  110.         solve();
  111.  
  112.  
  113. return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement