Advertisement
Josif_tepe

Untitled

Apr 23rd, 2023
843
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <map>
  7. #include <stack>
  8. using namespace std;
  9.  
  10.  
  11. using namespace std;
  12.  
  13. const int maxn=350005;
  14. int n;
  15. vector<int>g[maxn];
  16. bool vis[maxn];
  17. vector<int>v;
  18. int st[3*maxn];
  19.  
  20. void btree(int L,int R,int pos)
  21. {
  22.     if(L==R)
  23.     {
  24.         st[pos]=0;
  25.         return ;
  26.     }
  27.     int mid=(L+R)/2;
  28.     btree(L,mid,2*pos);
  29.     btree(mid+1,R,2*pos+1);
  30.     st[pos]=st[2*pos]+st[2*pos+1];
  31. }
  32.  
  33. void u(int L,int R,int idx,int pos)
  34. {
  35.     if(L==R)
  36.     {
  37.         st[pos]=1;
  38.         return ;
  39.     }
  40.     int mid=(L+R)/2;
  41.     if(idx<=mid)
  42.     {
  43.         u(L,mid,idx,2*pos);
  44.     }
  45.     else
  46.     {
  47.         u(mid+1,R,idx,2*pos+1);
  48.     }
  49.     st[pos]=st[2*pos]+st[2*pos+1];
  50. }
  51.  
  52. int query(int L,int R,int i,int j,int pos)
  53. {
  54.     //L  R   i L R j L R
  55.     if(i<=L && R<=j)
  56.     {
  57.         return st[pos];
  58.     }
  59.     if(j<L || R<i)
  60.     {
  61.         return 0;
  62.     }
  63.     int mid=(L+R)/2;
  64.     return query(L,mid,i,j,2*pos)+query(mid+1,R,i,j,2*pos+1);
  65. }
  66.  
  67. void topsort(int node)
  68. {
  69.     vis[node]=true;
  70.     for(auto a:g[node])
  71.     {
  72.         if(!vis[a])
  73.         {
  74.             topsort(a);
  75.         }
  76.     }
  77.     v.push_back(node);
  78. }
  79.  
  80. int main()
  81. {
  82.     ios_base::sync_with_stdio(false);
  83.     cin>>n;
  84.     memset(vis,0,sizeof vis);
  85.     for(int i=1;i<=n;i++)
  86.     {
  87.         char c;
  88.         cin>>c;
  89.         if(c=='K')
  90.         {
  91.             g[i-1].push_back(i-1);
  92.         }
  93.         else
  94.         {
  95.             int num;
  96.             cin>>num;
  97.             g[num-1].push_back(i-1);
  98.         }
  99.     }
  100.     for(int idx=0;idx<n;idx++)
  101.     {
  102.         if(!vis[idx])
  103.         {
  104.             topsort(idx);
  105.         }
  106.     }
  107.     btree(0,n,1);
  108.     vector<pair<int,int>>ans;
  109.     for(int i=0;i<n;i++)
  110.     {
  111.         u(0,n, v[i], 1);
  112.         ans.push_back({v[i],query(0,n,0,v[i],1)});
  113.     }
  114.     sort(ans.begin(),ans.end());
  115.     for(int i=0;i<n;i++)
  116.     {
  117.         cout<<ans[i].second<<"\n";
  118.     }
  119.     return 0;
  120. }
  121.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement