Submission #679129

#	Time	Username	Problem	Language	Result	Execution time	Memory
679129		cadmiumsky	Rectangles (IOI19_rect)	C++14	0 / 100	786 ms	343936 KiB

rect

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

#define sz(x) (int)(x).size()

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 25e2 + 5, inf = 1e9 + 5;

int dirx[4] = {1, -1, 0, 0};
int diry[4] = {0, 0, 1, -1};
vector<vector<int>> mat, tmp;

vector<pii> list[nmax * nmax];

int n, m, maxv;

#define y1 rgbuih
int x1, x2, y1, y2;

void dfs(int x, int y) {
  if(tmp[x][y] != 0) return;
  x1 = min(x, x1);
  y1 = min(y, y1);
  x2 = max(x, x2);
  y2 = max(y, y2);
  tmp[x][y] = 1;
  
  for(int h = 0; h < 4; h++)
    dfs(x + dirx[h], y + diry[h]);
  return;
}

ll countforlim(int lim) {
  tmp = mat;
  vector<vector<int>> spart(n + 2, vector<int>(m + 2, 0));
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++)
      tmp[i][j] = tmp[i][j] > lim,
      spart[i][j] += spart[i - 1][j] + spart[i][j - 1] - spart[i - 1][j - 1];
  }
  
  ll count = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      if(tmp[i][j] != 1 && mat[i][j] == lim) {
	x1 = n + 1, 
	x2 = 0,
	y1 = m + 1,
	y2 = 0;
	dfs(i, j);
	if(spart[x2][y2] - spart[x1 - 1][y2] - spart[x2][y1 - 1] + spart[x1 - 1][y1 - 1] == 0 && x1 > 1 && x2 < n && y1 > 1 && y2 < m) {
	  count++;
	  //cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\t' << lim << ' ' << mat[x1][y1] << '\n';
	}
      }
    }
  }
  return count;
}

long long count_rectangles(std::vector<std::vector<int> > initmat) {

  { // normalizare
    map<int,int> nrm;
    for(auto &v : initmat) {
      for(auto &x : v)
	nrm[x];
    }
    
    int cnt = 0;
    for(auto &[a, b] : nrm) b = cnt++;
    
    for(auto &v : initmat) {
      for(auto &x : v)
	x = nrm[x];
    }
    maxv = cnt - 1;
  }
 
  n = initmat.size();
  m = initmat[0].size();
  
  mat.resize(n + 2, vector<int>(m + 2, inf));
  
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      mat[i][j] = initmat[i - 1][j - 1];
    }
  }
  
  //for(auto v : mat) {
    //for(auto x : v)
      //cerr << x << ' ';
    //cerr << '\n';
  //}
  ll total = 0;
  
  for(int u = 0; u <= maxv; u++) { // a se schimba la <= maxv
    total += countforlim(u);
  }
  return total;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:76:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for(auto &[a, b] : nrm) b = cnt++;
      |               ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28