fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. #define saleh                         \
  7.     ios_base::sync_with_stdio(false); \
  8.     cin.tie(nullptr);
  9. #define ll long long
  10.  
  11. int n;
  12.  
  13. struct node
  14. {
  15.     int l = -1, r = -1;
  16. };
  17.  
  18. struct segTree
  19. {
  20.     int size;
  21.     vector<int> segData;
  22.  
  23.     void build(int n)
  24.     {
  25.         size = 1;
  26.         while (size < n)
  27.             size *= 2;
  28.         segData.assign(2 * size, 0);
  29.     }
  30.  
  31.     void update(int ind, int x, int lx, int rx)
  32.     {
  33.         if (rx - lx == 1)
  34.         {
  35.             segData[x] = 0;
  36.             return;
  37.         }
  38.         int mid = (lx + rx) / 2;
  39.         if (ind < mid)
  40.         {
  41.             update(ind, 2 * x + 1, lx, mid);
  42.         }
  43.         else
  44.         {
  45.             update(ind, 2 * x + 2, mid, rx);
  46.         }
  47.         segData[x] = segData[2 * x + 1] + segData[2 * x + 2];
  48.     }
  49.     void update(int ind)
  50.     {
  51.         update(ind, 0, 0, size);
  52.     }
  53.  
  54.     int queury(int l, int r, int x, int lx, int rx)
  55.     {
  56.         if (lx >= r || l >= rx)
  57.             return 0;
  58.         if (lx >= l && rx <= r)
  59.             return segData[x];
  60.  
  61.         int mid = (lx + rx) / 2;
  62.         int leftpart = queury(l, r, 2 * x + 1, lx, mid);
  63.         int rightpart = queury(l, r, 2 * x + 2, mid, rx);
  64.         return leftpart + rightpart;
  65.     }
  66.  
  67.     int queury(int l, int r)
  68.     {
  69.         return queury(l, r, 0, 0, size);
  70.     }
  71.  
  72.     void build(int x, int lx, int rx)
  73.     {
  74.         if (rx - lx == 1)
  75.         {
  76.             if (lx < 2 * n)
  77.             {
  78.                 segData[x] = 1;
  79.             }
  80.  
  81.             return;
  82.         }
  83.         int mid = (lx + rx) / 2;
  84.         build(2 * x + 1, lx, mid);
  85.         build(2 * x + 2, mid, rx);
  86.         segData[x] = segData[2 * x + 1] + segData[2 * x + 2];
  87.     }
  88.     void buildons()
  89.     {
  90.         build(0, 0, size);
  91.     }
  92. };
  93.  
  94. void solve()
  95. {
  96.     cin >> n;
  97.  
  98.     vector<node> p(n);
  99.     vector<int> v(n * 2);
  100.     for (int i = 0; i < n * 2; i++)
  101.     {
  102.         cin >> v[i];
  103.         v[i]--;
  104.     }
  105.  
  106.     for (int i = 0; i < n * 2; i++)
  107.     {
  108.         int x = v[i];
  109.         if (p[x].l == -1)
  110.             p[x].l = i;
  111.         else
  112.             p[x].r = i;
  113.     }
  114.  
  115.     segTree segment;
  116.     segment.build(n * 2);
  117.     segment.buildons();
  118.  
  119.     vector<int> result(n);
  120.  
  121.     for (int i = 0; i < n * 2; i++)
  122.     {
  123.         if (p[v[i]].l != -1)
  124.         {
  125.             result[v[i]] = ((segment.queury(p[v[i]].l + 1, p[v[i]].r)) / 2);
  126.             segment.update(p[v[i]].l);
  127.             segment.update(p[v[i]].r);
  128.             p[v[i]].l = -1;
  129.         }
  130.     }
  131.     for (auto a : result)
  132.         cout << a << " ";
  133. }
  134.  
  135. int main()
  136. {
  137.     saleh;
  138.     solve();
  139.     return 0;
  140. }
  141.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/POX1Sh
language:
C++ (gcc 8.3)
created:
80 days 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!