fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33. /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
  34.  
  35. const int MOD = 1e9 + 7;
  36. const int inf = 1e9 + 27092008;
  37. const ll INF = 1e18 + 27092008;
  38. const int N = 2e5 + 5;
  39. int n, a[N], par[N][20];
  40. int f[N], L[N], R[N], depth[N], lca[N];
  41.  
  42. int LCA(int u, int v) {
  43.     if (depth[u] < depth[v]) swap(u, v);
  44.     int s = depth[u] - depth[v];
  45.     REP(j, 20) if (BIT(s, j))
  46.         u = par[u][j];
  47.     if (u == v) return u;
  48.     RED(j, 20) if (par[u][j] != par[v][j]) {
  49.         u = par[u][j];
  50.         v = par[v][j];
  51.     }
  52.     return par[u][0];
  53. }
  54.  
  55. int ft[2 * N];
  56. void update(int x, int val) {
  57.     for(; x <= 2 * n + 1; x += x & -x) maximize(ft[x], val);
  58. }
  59.  
  60. int get(int x) {
  61.     int ans = 0;
  62.     for(; x; x -= x & -x) maximize(ans, ft[x]);
  63.     return ans;
  64. }
  65.  
  66. vector<int> mn[2 * N], mx[2 * N], vals[2 * N];
  67.  
  68. void update2(vector<int> &ft, int x, int val) {
  69.     for(; x <= (int)ft.size() - 1; x += x & -x) maximize(ft[x], val);
  70. }
  71.  
  72. int get2(vector<int> &ft, int x) {
  73.     int ans = -inf;
  74.     for(; x; x -= x & -x) maximize(ans, ft[x]);
  75.     return ans;
  76. }
  77.  
  78. void calc(int a[], int L[]) {
  79. //    FOR(i, 1, n) cerr << a[i] << ' '; cerr << '\n';
  80.     FOR(i, 1, n) f[i] = depth[i] = L[i] = lca[i] = par[i][0] = 0;
  81.     FOR(i, 1, 2 * n + 1) {
  82.         ft[i] = 0;
  83.         mn[i].clear();
  84.         mx[i].clear();
  85.         vals[i].clear();
  86.     }
  87.  
  88.     FOR(i, 1, n) {
  89.         f[i] = get(a[i] - 1) + 1;
  90.         update(a[i], f[i]);
  91.         vals[f[i]].pb(a[i]);
  92.     }
  93.  
  94.     FOR(i, 1, n) {
  95.         sort(all(vals[i]));
  96.         mn[i].assign((int)vals[i].size() + 5, -inf);
  97.         mx[i].assign((int)vals[i].size() + 5, 0);
  98.     }
  99.  
  100.     FOR(i, 1, n) {
  101.         int p = 0;
  102.         if (f[i] > 1) {
  103.             int val = f[i] - 1;
  104.             int pos = lower_bound(all(vals[val]), a[i]) - vals[val].begin();
  105. //            cerr << val << ' ' << a[i] << ' ' << pos << '\n';
  106.             int minJ = min(n + 1, -get2(mn[val], pos));
  107.             int maxJ = get2(mx[val], pos);
  108.             p = LCA(minJ, maxJ);
  109. //            cerr << i << ' ' << f[i] << ' ' << minJ << ' ' << maxJ << '\n';
  110.         }
  111.  
  112.         int tmp = upper_bound(all(vals[f[i]]), a[i]) - vals[f[i]].begin();
  113. //        cerr << "UPDATE : " << i << ' ' << tmp << '\n';
  114.         update2(mn[f[i]], tmp, -i);
  115.         update2(mx[f[i]], tmp, i);
  116. //        cerr << "GET : " << i << ' ' << tmp << ' ' << mn[f[i]][2] << ' ' << get2(mn[f[i]], tmp) << ' ' << get2(mx[f[i]], tmp) << '\n';
  117.  
  118.         if (p > 0) L[i] = L[p] + 1;
  119.         depth[i] = depth[p] + 1;
  120.         par[i][0] = p;
  121.         FOR(t, 1, 19) par[i][t] = par[par[i][t - 1]][t - 1];
  122.     }
  123. }
  124.  
  125. void init(void) {
  126.     cin >> n;
  127.     FOR(i, 1, n) cin >> a[i];
  128. }
  129.  
  130. void process(void) {
  131.     calc(a, L);
  132.     reverse(a + 1, a + n + 1);
  133.     FOR(i, 1, n) a[i] = n-a[i]+1;
  134.     calc(a, R);
  135.  
  136.     FOR(i, 1, n) cout << L[i] + R[n - i + 1] << ' ';
  137. }
  138.  
  139. int main() {
  140.     ios_base::sync_with_stdio(0);
  141.     cin.tie(0); cout.tie(0);
  142.     if (fopen(task".inp", "r")) {
  143.         freopen(task".inp", "r", stdin);
  144.         freopen(task".out", "w", stdout);
  145.     }
  146.     int tc = 1;
  147. //    cin >> tc;
  148.     while(tc--) {
  149.         init();
  150.         process();
  151.     }
  152.     return 0;
  153. }
  154.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sK426w
language:
C++14 (gcc 8.3)
created:
3 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!