fork download
copy 
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3. # define fi cin
  4. # define fo cout
  5. # define x first
  6. # define y second
  7. # define IOS ios_base :: sync_with_stdio(0)
  8. int s[1 << 20];
  9. int v[1 << 20];
  10. pair < int , int > t[1 << 22];
  11. void build(int p,int u,int node)
  12. {
  13.     if (p == u) t[node] = {v[p],p};
  14.     else
  15.     {
  16.         int m = (p + u) / 2;
  17.         build(p,m,node << 1);
  18.         build(m+1,u,node << 1 | 1);
  19.         t[node] = max(t[node << 1],t[node << 1 | 1]);
  20.     }
  21. }
  22. void Del(int p,int u,int v,int node)
  23. {
  24.     if (p == u) t[node] = {0,p};
  25.     else
  26.     {
  27.         int m = (p + u) / 2;
  28.         if (v <= m) Del(p,m,v,node << 1);
  29.         else Del(m+1,u,v,node << 1 | 1);
  30.         t[node] = max(t[node << 1],t[node << 1 | 1]);
  31.     }
  32. }
  33. pair < int , int > query(int p,int u,int l,int r,int node)
  34. {
  35.     if (l > r) return {0,0};
  36.     if (l <= p && u <= r) return t[node];
  37.     int m = (p + u) / 2;
  38.     pair < int , int > ans = {0,0};
  39.     if (l <= m) ans = max(ans,query(p,m,l,r,node << 1));
  40.     if (m+1<=r) ans = max(ans,query(m+1,u,l,r,node << 1 | 1));
  41.     return ans;
  42. }
  43. int was[1 << 20];
  44. int n;
  45. vector < int > Sort;
  46. void dfs(int node)
  47. {
  48.     Del(1,n,node,1);
  49.     was[node] = 1;
  50.     if (v[node] != n + 1 && !was[v[node]]) dfs(v[node]);
  51.     while (1)
  52.     {
  53.         auto it = query(1,n,1,s[node] - 1,1);
  54.         if (it.x > node) dfs(it.y);
  55.         else break;
  56.     }
  57.     Sort.push_back(node);
  58. }
  59. int ans[1 << 20];
  60. int main(void)
  61. {
  62.     scanf("%d\n",&n);
  63.     for (int i = 1;i <= n;++i) v[i] = n + 1;
  64.     for (int i = 1;i <= n;++i) scanf("%d",&s[i]);
  65.     for (int i = 1;i <= n;++i)
  66.         if (s[i] != -1)
  67.             v[s[i]] = i;
  68.     for (int i = 1;i <= n;++i)
  69.         if (s[i] == -1)
  70.             s[i] = n + 1;
  71.     build(1,n,1);
  72.     for (int i = 1;i <= n;++i)
  73.         if (!was[i])
  74.             dfs(i);
  75.     int cnt = 0;
  76.     for (auto it : Sort)
  77.         ans[it] = ++cnt;
  78.     for (int i = 1;i <= n;++i)
  79.         printf("%d%c",ans[i]," \n"[i == n]);
  80.     return 0;
  81. }
  82.  
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mBKErn
language:
C++14 (gcc 8.3)
created:
7 years 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!