fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(x) begin(x), end(x)
  3. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  4. #define FOD(i, r, l, x) for(int i = r; i >= l; i -= x)
  5. #define pub push_back
  6. #define pii pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define int long long
  10. #define x1 x_1
  11. #define y1 y_1
  12. #define x2 x_2
  13. #define y2 y_2
  14. using namespace std;
  15.  
  16. const int N = 5e5 + 5;
  17. const int MAX = 1e6 + 5;
  18. const int M = 1005;
  19. const int mod = 1e9;
  20. const long long inf = 2e18;
  21.  
  22. int n, m, q, k, a[M][M], st[4 * M], out[N];
  23. vector <pii> vec[N];
  24.  
  25. void upd(int id, int l, int r, int pos, int val) {
  26.     if (!(l <= pos && pos <= r)) return;
  27.     if (l == r) {
  28.         st[id] = val;
  29.         return;
  30.     }
  31.  
  32.     int mid = (l + r) >> 1;
  33.  
  34.     upd(id << 1, l, mid, pos, val);
  35.     upd(id << 1 | 1, mid + 1, r, pos, val);
  36.  
  37.     st[id] = max(st[id << 1], st[id << 1 | 1]);
  38. }
  39. int get(int id, int l, int r, int u, int v) {
  40.     if (r < u || v < l) return -inf;
  41.     if (u <= l && r <= v) return st[id];
  42.  
  43.     int mid = (l + r) >> 1;
  44.  
  45.     int m1 = get(id << 1, l, mid, u, v);
  46.     int m2 = get(id << 1 | 1, mid + 1, r, u, v);
  47.  
  48.     return max(m1, m2);
  49. }
  50. void solve() {
  51.     cin >> n;
  52.     FOR(i, 1, n, 1) FOR(j, 1, n, 1) {
  53.         cin >> a[i][j];
  54.         vec[a[i][j]].pub({i, j});
  55.     }
  56.  
  57.     FOR(i, 1, n, 1) FOR(j, 1, n, 1) {
  58.         int val = a[i][j];
  59.         int nn  = vec[val].size();
  60.         int ans = 0;
  61.         vector <int> dp1(nn + 2, 0);
  62.         vector <int> dp2(nn + 2, 0);
  63.         int pos = 0;
  64.  
  65.         FOR(k, 0, nn - 1, 1) {
  66.             dp1[k] = 1;
  67.             int y = vec[val][k].se;
  68.  
  69.             if (vec[val][k].fi == i && vec[val][k].se == j) pos = k;
  70.  
  71.             if (k > 0) {
  72.                 dp1[k] = max(dp1[k], get(1, 1, 705, 1, y) + 1);
  73.             }
  74.  
  75.             upd(1, 1, 705, y, dp1[k]);
  76.         }
  77.  
  78.         FOR(k, 0, nn - 1, 1) {
  79.             int y = vec[val][k].se;
  80.             upd(1, 1, 705, y, 0);
  81.         }
  82.  
  83.         FOD(k, nn - 1, 0, 1) {
  84.             dp2[k] = 1;
  85.             int y = vec[val][k].se;
  86.             if (vec[val][k].fi == i && vec[val][k].se == j) pos = k;
  87.  
  88.             if (k < nn - 1) {
  89.                 dp2[k] = max(dp2[k], get(1, 1, 705, y, 705) + 1);
  90.             }
  91.  
  92.             upd(1, 1, 705, y, dp2[k]);
  93.         }
  94.  
  95.         FOD(k, nn - 1, 0, 1) {
  96.             int y = vec[val][k].se;
  97.             upd(1, 1, 705, y, 0);
  98.         }
  99.  
  100.         ans = dp1[pos] + dp2[pos] - 1;
  101.         out[ans]++;
  102.     }
  103.     FOR(i, 1, 2 * n - 1, 1) {
  104.         cout << out[i] << '\n';
  105.     }
  106. }
  107. signed main() {
  108.     #define name "baitap"
  109.     if (ifstream(name".inp")) {
  110.         freopen(name".inp", "r", stdin);
  111.         freopen(name".out", "w", stdout);
  112.     }
  113.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  114.     solve();
  115. }
  116.  
Success #stdin #stdout 0.01s 15720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VYWKzT
language:
C++ (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!