API tools faq
paste
Abrar_Al_Samit

Promotion Counting (USACO Jan 2017 Platinum)

Abrar_Al_Samit
Jul 16th, 2021 (edited)
176
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.81 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8.  
  9. #define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';
  10.  
  11. template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
  12.  
  13. const int maxn = 1e5 + 5;
  14. vector<int>g[maxn];
  15. void PlayGround() {
  16.     int n; cin >> n;
  17.     int p[n+1], v[n+1];
  18.     for(int i=1; i<=n; ++i) cin >> v[i];
  19.     for(int i=2; i<=n; ++i) {
  20.         int pa; cin >> pa;
  21.         g[pa].push_back(i);
  22.     }
  23.     int timer = 1;
  24.     int st[n+1], en[n+1];
  25.     function<void(int,int)> DFS = [&] (int node, int parent) {
  26.         st[node] = timer++;
  27.         for(auto it : g[node]) DFS(it, node);
  28.         en[node] = timer - 1;
  29.     };
  30.     DFS(1, 1);
  31.     for(int node=1; node <= n; ++node) p[st[node]] = v[node];
  32.  
  33.     vector<vector<int>>segmentTree(n<<2, vector<int>());
  34.     auto merge = [=] (vector<int>a, vector<int>b) {
  35.         int p0 = 0, p1 = 0;
  36.         int n = a.size(), m = b.size();
  37.         vector<int>ret;
  38.         while(p0<n || p1<m) {
  39.             if(p0==n) {
  40.                 ret.push_back(b[p1++]);
  41.             } else if(p1==m) {
  42.                 ret.push_back(a[p0++]);
  43.             } else {
  44.                 if(a[p0]<=b[p1]) ret.push_back(a[p0++]);
  45.                 else ret.push_back(b[p1++]);
  46.             }
  47.         }
  48.         assert(is_sorted(ret.begin(), ret.end()));
  49.         return ret;
  50.     };
  51.     function<void(int,int,int)> Build = [&] (int l, int r, int node) {
  52.         if(l==r) {
  53.             segmentTree[node].push_back(p[l]);
  54.             return;
  55.         }
  56.         int mid = (l+r)>>1;
  57.         Build(l, mid, node+node);
  58.         Build(mid+1, r, node+node+1);
  59.         segmentTree[node] = merge(segmentTree[node+node], segmentTree[node+node+1]);
  60.     };
  61.     Build(1, n, 1);
  62.     function<int(int,int,int,int,int,int)> Query = [&] (int l, int r, int L, int R, int val, int node) {
  63.         if(l>=L && r<=R) {
  64.             return (int)(segmentTree[node].end() - upper_bound(segmentTree[node].begin(), segmentTree[node].end(), val));
  65.         }
  66.         if(l>R || r<L) return 0;
  67.         int mid = (l+r)>>1;
  68.         return Query(l, mid, L, R, val, node+node) + Query(mid+1, r, L, R, val, node+node+1);
  69.     };
  70.     for(int node=1; node<=n; ++node)
  71.         cout << Query(1, n, st[node], en[node], p[st[node]], 1) << '\n';
  72.  
  73.  
  74.     #ifndef ONLINE_JUDGE
  75.         cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  76.     #endif
  77. }
  78. int main() {
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);
  81.     cout.tie(0);
  82.     #ifndef ONLINE_JUDGE
  83.         //freopen("input.txt", "r", stdin);
  84.         freopen("promote.in", "r", stdin);
  85.         freopen("promote.out", "w", stdout);
  86.     #endif
  87.     PlayGround();
  88.  
  89.     return 0;
  90. }
Add Comment
Please, Sign In to add comment
Public Pastes
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!