fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn = 2e6 + 5;
  5. #define int long long
  6.  
  7. int n, m, k, ok[maxn];
  8. vector<vector<int>> pre;
  9. pair<int, int> dd[maxn];
  10.  
  11. struct node{
  12.     int i, j, u, v;
  13.     node() {
  14.         i = j = 1e9;
  15.         u = v = 0;
  16.     }
  17. };
  18.  
  19. node val[maxn];
  20.  
  21. int get(int i, int j, int u, int v) {
  22.     if(i > u || j > v) return 0;
  23.     return pre[u][v] - pre[u][j - 1]
  24.          - pre[i - 1][v] + pre[i - 1][j - 1];
  25. }
  26.  
  27. bool okk(int x, int i, int j, int u, int v) {
  28.     int fi = dd[x].first;
  29.     int se = dd[x].second;
  30.  
  31.     if(fi < i || fi > u || se < j || se > v)
  32.         return false;
  33.  
  34.     return true;
  35. }
  36.  
  37. signed main () {
  38.     //freopen("hcn.inp", "r", stdin);
  39.     //freopen("hcn.out", "w", stdout);
  40.  
  41.     ios_base::sync_with_stdio(0);
  42.     cin.tie(0);
  43.  
  44.     cin >> n >> m >> k;
  45.  
  46.     vector<vector<int>> a;
  47.     a.resize(n + 1);
  48.     pre.resize(n + 1);
  49.  
  50.     for(int i = 0; i <= n; i++)
  51.         a[i].resize(m + 1),
  52.         pre[i].resize(m + 1);
  53.  
  54.     for(int i = 1; i <= n; i++) {
  55.         for(int j = 1; j <= m; j++) {
  56.  
  57.             cin >> a[i][j];
  58.  
  59.             int x = a[i][j];
  60.  
  61.             pre[i][j] = pre[i - 1][j]
  62.                       + pre[i][j - 1]
  63.                       - pre[i - 1][j - 1];
  64.  
  65.             if(!ok[x]) {
  66.                 pre[i][j]++;
  67.                 ok[x] = 1;
  68.                 dd[x] = {i, j};
  69.             }
  70.  
  71.             val[x].i = min(val[x].i, i);
  72.             val[x].j = min(val[x].j, j);
  73.             val[x].u = max(val[x].u, i);
  74.             val[x].v = max(val[x].v, j);
  75.         }
  76.     }
  77.  
  78.     for(int i = 1; i <= k; i++)
  79.         ok[i] = 0;
  80.  
  81.     for(int num = 1; num <= k; num++) {
  82.  
  83.         int i = val[num].i;
  84.         int j = val[num].j;
  85.         int u = val[num].u;
  86.         int v = val[num].v;
  87.  
  88.         int ans = get(i + 1, j + 1, u - 1, v - 1);
  89.  
  90.         int ii = dd[num].first;
  91.         int jj = dd[num].second;
  92.  
  93.         if(ii >= i + 1 && ii <= u - 1 &&
  94.            jj >= j + 1 && jj <= v - 1)
  95.             ans--;
  96.  
  97.         ok[num] = 1;
  98.  
  99.         // Trường hợp không có interior
  100.         if(i + 1 > u - 1 || j + 1 > v - 1) {
  101.  
  102.             vector<int> P;
  103.  
  104.             for(int hang = i; hang <= u; hang++) {
  105.                 for(int cot = j; cot <= v; cot++) {
  106.  
  107.                     if(!ok[a[hang][cot]]) {
  108.                         ans++;
  109.                         ok[a[hang][cot]] = 1;
  110.                         P.push_back(a[hang][cot]);
  111.                     }
  112.                 }
  113.             }
  114.  
  115.             cout << ans << " ";
  116.  
  117.             for(auto x : P)
  118.                 ok[x] = 0;
  119.  
  120.             ok[num] = 0;
  121.  
  122.             continue;
  123.         }
  124.  
  125.         vector<int> P;
  126.  
  127.         // hang(i)
  128.         for(int cot = j + 1; cot <= v - 1; cot++) {
  129.  
  130.             int x = a[i][cot];
  131.  
  132.             if(!ok[x] && !okk(x, i + 1, j + 1, u - 1, v - 1)) {
  133.                 ans++;
  134.                 ok[x] = 1;
  135.                 P.push_back(x);
  136.                 continue;
  137.             }
  138.  
  139.             if(!ok[x] &&
  140.                (x != a[i + 1][cot] || i + 1 >= u)) {
  141.  
  142.                 ans++;
  143.                 ok[x] = 1;
  144.                 P.push_back(x);
  145.             }
  146.         }
  147.  
  148.         // hang(u)
  149.         for(int cot = j + 1; cot <= v - 1; cot++) {
  150.  
  151.             int x = a[u][cot];
  152.  
  153.             if(!ok[x] && !okk(x, i + 1, j + 1, u - 1, v - 1)) {
  154.                 ans++;
  155.                 ok[x] = 1;
  156.                 P.push_back(x);
  157.                 continue;
  158.             }
  159.  
  160.             if(!ok[x] &&
  161.                (x != a[u - 1][cot] || u - 1 <= i)) {
  162.  
  163.                 ans++;
  164.                 ok[x] = 1;
  165.                 P.push_back(x);
  166.             }
  167.         }
  168.  
  169.         // cot(j)
  170.         for(int hang = i + 1; hang <= u - 1; hang++) {
  171.  
  172.             int x = a[hang][j];
  173.  
  174.             if(!ok[x] && !okk(x, i + 1, j + 1, u - 1, v - 1)) {
  175.                 ans++;
  176.                 ok[x] = 1;
  177.                 P.push_back(x);
  178.                 continue;
  179.             }
  180.  
  181.             if(!ok[x] &&
  182.                (x != a[hang][j + 1] || j + 1 >= v)) {
  183.  
  184.                 ans++;
  185.                 ok[x] = 1;
  186.                 P.push_back(x);
  187.             }
  188.         }
  189.  
  190.         // cot(v)
  191.         for(int hang = i + 1; hang <= u - 1; hang++) {
  192.  
  193.             int x = a[hang][v];
  194.  
  195.             if(!ok[x] && !okk(x, i + 1, j + 1, u - 1, v - 1)) {
  196.                 ans++;
  197.                 ok[x] = 1;
  198.                 P.push_back(x);
  199.                 continue;
  200.             }
  201.  
  202.             if(!ok[x] &&
  203.                (x != a[hang][v - 1] || v - 1 <= j)) {
  204.  
  205.                 ans++;
  206.                 ok[x] = 1;
  207.                 P.push_back(x);
  208.             }
  209.         }
  210.  
  211.         // 4 góc
  212.         for(auto hang : {i, u}) {
  213.             for(auto cot : {j, v}) {
  214.  
  215.                 if(!ok[a[hang][cot]]) {
  216.                     ans++;
  217.                     P.push_back(a[hang][cot]);
  218.                     ok[a[hang][cot]] = 1;
  219.                 }
  220.             }
  221.         }
  222.  
  223.         cout << ans << ' ';
  224.  
  225.         for(auto x : P)
  226.             ok[x] = 0;
  227.  
  228.         ok[num] = 0;
  229.     }
  230. }
  231.  
Success #stdin #stdout 0.02s 98592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ppVu9R
language:
C++14 (clang 8.0)
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!