fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,a[702][702],cnt[1836],st[6767],L[2][500005];
  4. vector <pair<int,int>> ve[500005];
  5. void UPDATE(int id, int l, int r, int i, int v)
  6. {
  7.     if (l>i || r<i) return;
  8.     else if (l==r)
  9.     {
  10.         st[id]=v;
  11.         return;
  12.     }
  13.     int mid=(l+r)/2;
  14.     if (i<=mid) UPDATE(id*2,l,mid,i,v);
  15.     else UPDATE(id*2+1,mid+1,r,i,v);
  16.     st[id]=max(st[id*2],st[id*2+1]);
  17. }
  18. int GET(int id, int l, int r, int u, int v)
  19. {
  20.     if (l>v || r<u) return -1e18;
  21.     else if (l>=u && r<=v) return st[id];
  22.     int mid=(l+r)/2;
  23.     return max(GET(id*2,l,mid,u,v),GET(id*2+1,mid+1,r,u,v));
  24. }
  25. void SOLVE(int x)
  26. {
  27.     for (int i=0;i<ve[x].size();i++)
  28.     {
  29.         int j=ve[x][i].second,mx=GET(1,1,n,1,j)+1;
  30.         if (GET(1,1,n,j,j)<mx) UPDATE(1,1,n,j,mx),L[0][i]=mx;
  31.     }
  32.     for (int i=0;i<ve[x].size();i++) UPDATE(1,1,n,ve[x][i].second,0);
  33.     for (int i=ve[x].size()-1;i>=0;i--)
  34.     {
  35.         int j=ve[x][i].second,mx=GET(1,1,n,j,n)+1;
  36.         if (GET(1,1,n,j,j)<mx) UPDATE(1,1,n,j,mx),L[1][i]=mx;
  37.     }
  38.     for (int i=0;i<ve[x].size();i++) UPDATE(1,1,n,ve[x][i].second,0);
  39.     for (int i=0;i<ve[x].size();i++) cnt[L[0][i]+L[1][i]-1]++,L[0][i]=L[1][i]=0;
  40. }
  41. signed main()
  42. {
  43.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  44.     cin>>n;
  45.     for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) cin>>a[i][j];
  46.     for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ve[a[i][j]].push_back({i,j});
  47.     for (int i=1;i<=n*n;i++) if (ve[i].size()) SOLVE(i);
  48.     for (int i=1;i<2*n;i++) cout<<cnt[i]<<'\n';
  49.     return 0;
  50. }
Success #stdin #stdout 0.01s 15664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rs4uIy
language:
C++14 (gcc 8.3)
created:
2 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!