Submission #679170

#	Time	Username	Problem	Language	Result	Execution time	Memory
679170		cadmiumsky	Rectangles (IOI19_rect)	C++14	0 / 100	1 ms	596 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>;

#warning Schimba
const int nmax = 5 + 5, inf = 1e9 + 5;

int n, m;

int dirx[4] = {1, -1, 0, 0};
int diry[4] = {0, 0, 1, -1};
vector<vector<int>> mat, tmp;
vector<int> lst;
vector<bitset<nmax>> blst;
bitset<nmax> online[nmax][nmax];

void addline(int line) {
  
  for(int i = 1; i <= m; i++)
    lst[i] = max(lst[i], mat[line][i]),
    blst[i] = blst[i] & online[line][i];
}


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

 
  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(int i = 2; i < n; i++) {
    vector<int> st;
    for(int j = 1; j <= m; j++) {
      online[i][j + 1] = online[i][j];
      while(!st.empty() && mat[i][st.back()] <= mat[i][j])
	online[i][j + 1][st.back()] = 0,
	st.pop_back();
      online[i][j + 1][j] = 1;
      online[i][j][j - 1] = 0;
      //for(auto x : st)
	//cerr << x << ' ';
      cerr << online[i][j];
      cerr << "  ";
      st.push_back(j);
    }
    cerr << '\n';
  }
  
  ll total = 0;
  
  for(int i1 = 1; i1 <= n; i1++) {
    lst.clear();
    blst.clear();
    lst.resize(m + 2, 0);
    blst.resize(m + 2, 0);
    for(auto &x : blst)
      x.set();
    addline(1 + 1);
    for(int i2 = i1 + 2; i2 <= n; i2++) {
      int lastbad = 1;
      for(int j = 2; j <= m; j++) {
	//cerr << lastbad << ' ' << i1 << ' ' << i2 << '\t' << blst[j] << ' ' << (blst[j] >> lastbad).count() << '\n';
	total += (blst[j] >> lastbad).count();
	if(lst[j] >= mat[i1][j] || lst[j] >= mat[i2][j])
	  lastbad = j;
      }
      addline(i2);
    }
  }
  
  //for(auto v : mat) {
    //for(auto x : v)
      //cerr << x << ' ';
    //cerr << '\n';
  //}
  //ll total = 0;
  
  //for(int u = 0; u < 1; u++) { // a se schimba la <= maxv
    //total += countforlim(u);
  //}
  return total;
}

Compilation message (stderr)

rect.cpp:12:2: warning: #warning Schimba [-Wcpp]
   12 | #warning Schimba
      |  ^~~~~~~

• 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