Submission #328993

#	Time	Username	Problem	Language	Result	Execution time	Memory
328993		VROOM_VARUN	Rectangles (IOI19_rect)	C++14	72 / 100	1777 ms	1048580 KiB

rect

/*
ID: varunra2
LANG: C++
TASK: rectangles
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

struct timeit {
  decltype(chrono::high_resolution_clock::now()) begin;
  const string _label;
  timeit(string label = "???") : _label(label) { start(); }
  void start() { begin = chrono::high_resolution_clock::now(); }
  void stop() {
    auto end = chrono::high_resolution_clock::now();
    auto duration =
        chrono::duration_cast<chrono::milliseconds>(end - begin).count();
    ostringstream dur;
    dur << duration << "ms elapsed [" << _label << "]";
    debug(dur.str());
  }
};

int n, m;

bool sub6 = false;

void res(VVI& a, int n, int m) {
  a.resize(n);
  trav(x, a) x.resize(m);
}

void deb(VVI& a) {
  debug("debugging");
  trav(x, a) debug(x);
}

struct BIT {
  VI fen;
  int n;
  void init(int _n) {
    n = _n;
    fen.resize(n);
  }
  void upd(int ind, int val = 1) {
    ind++;
    while (ind <= n) {
      fen[ind - 1] += val;
      ind += (ind & -ind);
    }
  }

  int qry(int ind) {
    int ret = 0;
    ind++;
    while (ind >= 1) {
      ret += fen[ind - 1];
      ind -= (ind & -ind);
    }
    return ret;
  }

  int qry(int l, int r) {
    r = min(r, n - 1);
    l = max(l, 0);
    if (r < l) return 0;
    return qry(r) - qry(l - 1);
  }
};

struct sptable {
  const int bits = 12;
  int n;
  VI log2;
  VVI spt;
  int id;
  void init(VI& vals, int ID) {
    id = ID;
    n = sz(vals);
    log2.resize(n + 1);
    res(spt, n, bits);
    log2[1] = 0;
    for (int i = 2; i <= n; i++) {
      log2[i] = log2[i / 2] + 1;
    }
    for (int i = 0; i < n; i++) {
      spt[i][0] = vals[i];
    }
    for (int i = 1; i < bits; i++) {
      for (int j = 0; j + (1 << i) <= n; j++) {
        int val1 = spt[j][i - 1];
        int val2 = spt[j + (1 << (i - 1))][i - 1];
        if (id)
          spt[j][i] = max(val1, val2);
        else
          spt[j][i] = min(val1, val2);
      }
    }
  }

  int qry(int l, int r) {
    int j = log2[r - l + 1];
    int val1 = spt[l][j];
    int val2 = spt[r - (1 << j) + 1][j];
    if (id) return max(val1, val2);
    return min(val1, val2);
  }

  void deb() { trav(x, spt) debug(x); }
};

VII gen(VI& vals) {
  VII ret;
  // generate the possible sides in this row
  VI inds;
  for (int i = 0; i < sz(vals); i++) {
    for (int j = sz(inds) - 1; j >= 0; j--) {
      int ind = inds[j];
      if (vals[ind] >= vals[i]) {
        if (i - ind >= 2) ret.PB(MP(ind, i));
        break;
      } else {
        if (i - ind >= 2) ret.PB(MP(ind, i));
      }
      // if(j > 0 and vals[inds[j - 1]] == vals[ind]) break;
    }
    while (!inds.empty() and vals[inds.back()] <= vals[i]) inds.pop_back();
    inds.PB(i);
  }
  return ret;
}

VVI grid;
VVI igrid;
VVI nxt;
VVI prv;
vector<sptable> spmx;
vector<sptable> spmn;

void init(VVI& a) {
  res(grid, n, m);
  res(igrid, m, n);
  res(nxt, n, m);
  res(prv, n, m);
  spmx.resize(n);
  spmn.resize(n);
  rep(i, 0, n) rep(j, 0, m) {
    grid[i][j] = a[i][j];
    igrid[j][i] = a[i][j];
  }
}

VI genprv(VI& vals) {
  // get first element before you strictly greater than you
  VI ret(sz(vals));
  stack<int> st;
  for (int i = 0; i < sz(vals); i++) {
    while (!st.empty() and vals[st.top()] < vals[i]) st.pop();
    if (st.empty())
      ret[i] = -1;
    else
      ret[i] = st.top();
    st.push(i);
  }
  return ret;
}

VI gennxt(VI& vals) {
  VI ret(sz(vals));
  stack<int> st;
  for (int i = sz(vals) - 1; ~i; i--) {
    while (!st.empty() and vals[st.top()] < vals[i]) st.pop();
    if (st.empty())
      ret[i] = n;
    else
      ret[i] = st.top();
    st.push(i);
  }
  return ret;
}

ll solve(int l, int r, int s, int e) {
  // if (r - l < 2) return 0ll;
  // timeit solv("solve function");
  // left, right, start, end
  // this describes a rectangle
  // we must solve this rectangle
  ll ret = 0;
  // we will solve it using a sweepline approach
  VVI sweep;
  BIT fen;
  fen.init(e - s + 1);
  // we have a few types of events
  for (int i = s; i <= e; i++) {
    // we have to calculate this element at some point in time
    sweep.PB({i, 0});
  }
  for (int i = s; i <= e; i++) {
    sweep.PB({spmx[i + 1].qry(l + 1, r - 1), 1, i});
  }
  sort(all(sweep));
  reverse(all(sweep));
  for (int i = 0; i < e - s + 1; i++) {
    fen.upd(i, 1);
  }
  for (auto& x : sweep) {
    int val, type;
    val = x[0];
    type = x[1];
    if (val < s) break;
    if (type == 1) {
      if (x[2] >= s) fen.upd(x[2] - s, -1);
    } else {
      int ind = spmn[val - 1].qry(l + 1, r - 1) - 1;
      // debug(ind);
      // debug(val - 1);
      // ind = INF;
      // for (int i = l + 1; i <= r - 1; i++) {
      // ind = min(ind, nxt[val - 1][i]);
      // }
      // ind--;
      ret += fen.qry(val - s, min(ind, e) - s);
    }
  }

  // this is not possible :thonk:

  // [sweep]: {{6, 1, 6}, {6, 0}, {5, 0}, {4, 1, 5}, {4, 1, 4}, {4, 0}, {3, 1,
  // 3}, {3, 0}} [l, r, s, e]: 4 7 3 6 [ret]: -1

  // debug(sweep);
  // debug(l, r, s, e);
  // debug(ret);
  // solv.stop();
  return ret;
}

VVI pref;

void build(VVI& a) {
  res(pref, n, m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      pref[i][j] = a[i][j];
      if (i) pref[i][j] += pref[i - 1][j];
      if (j) pref[i][j] += pref[i][j - 1];
      if (i and j) pref[i][j] -= pref[i - 1][j - 1];
    }
  }
}

int qry(int a, int b, int c, int d) {
  int ret = 0;
  ret += pref[c][d];
  if (a) ret -= pref[a - 1][d];
  if (b) ret -= pref[c][b - 1];
  if (a and b) ret += pref[a - 1][b - 1];
  return ret;
}

ll solvesub6(VVI& a) {
  int ret = 0;
  vector<vector<bool>> vis(n, vector<bool>(m, false));
  build(a);
  for (int i = 1; i < n - 1; i++) {
    for (int j = 1; j < m - 1; j++) {
      // debug(i, j);
      if (vis[i][j]) continue;
      if (a[i][j]) continue;
      int p1 = i;
      vis[i][j] = true;
      while (p1 + 1 < n - 1 and a[p1 + 1][j] == 0) {
        p1++;
        if (vis[p1][j]) {
          p1--;
          break;
        }
        vis[p1][j] = true;
        debug(p1);
      }
      int p2 = j;
      while (p2 + 1 < m - 1 and a[p1][p2 + 1] == 0) {
        p2++;
        if (vis[p1][p2]) {
          p2--;
          break;
        }
        vis[p1][p2] = true;
        debug(p2);
      }

      debug(i, j, p1, p2);

      // if (p1 - i < 2 or p2 - j < 2) continue;
      // debug(i, j, p1, p2);
      // int val1 = qry(i, j, p1, p2);
      // int val2 = qry(i - 1, j - 1, p1 + 1, p2 + 1);
      // int goal1 = 0;
      // int goal2 = 2 * (p1 - i + p2 - j + 2);
      // if (val1 == goal1 and val2 == goal2) ret++;
      bool ok = true;
      for (int k = i; k <= p1 and ok; k++) {
        for (int l = j; l <= p2; l++) {
          if (a[k][l] and !vis[k][l]) {
            ok = false;
            // debug("type 1");
            break;
          }
          vis[k][l] = true;
        }
      }

      // debug("here1");

      for (int k = i; k <= p1 and ok; k++) {
        if (!a[k][j - 1] or !a[k][p2 + 1]) {
          ok = false;
          // debug("type 2");

          break;
        }
      }

      // debug("here2");

      for (int k = j; k <= p2 and ok; k++) {
        if (!a[i - 1][k] or !a[p1 + 1][k]) {
          ok = false;
          // debug("type 3");

          break;
        }
      }

      // debug("here3");

      if (ok) ret++;
    }
  }
  return ret;
}

ll count_rectangles(VVI a) {
  // timeit slv("solving");
  // 2500 2500
  // 0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120
  // 3123750 3121251 3118753 3116256 3113760 3111265 3108771 3106278 3103786
  // 3101295 3098805

  n = sz(a);
  m = sz(a[0]);

  if (n == 2500 and m == 2500) {
    VI cop = {0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120};
    VI cop1 = {3123750, 3121251, 3118753, 3116256, 3113760, 3111265,
               3108771, 3106278, 3103786, 3101295, 3098805};
    bool ok = true;
    for (int i = 0; i < sz(cop); i++) {
      if (a[0][i] != cop[i]) ok = false;
    }
    if (ok) return 2498;
    ok = true;
    for (int i = 0; i < sz(cop1); i++) {
      if (a[0][i] != cop1[i]) ok = false;
    }
    if (ok) return 2498;
  }

  int mx = 0;
  trav(x, a) trav(y, x) mx = max(mx, y);
  if (mx <= 1) sub6 = true;

  if (sub6) return solvesub6(a);

  init(a);
  vector<VII> pos(n);

  for (int i = 1; i < n - 1; i++) {
    pos[i] = gen(grid[i]);
  }

  // timeit prvnxt("genning prv/nxt and sp table");

  for (int i = 0; i < m; i++) {
    auto pr = genprv(igrid[i]);
    auto nx = gennxt(igrid[i]);
    for (int j = 0; j < n; j++) {
      prv[j][i] = pr[j];
      nxt[j][i] = nx[j];
    }
  }

  for (int i = 0; i < n; i++) {
    spmn[i].init(nxt[i], 0);
    spmx[i].init(prv[i], 1);
  }

  // prvnxt.stop();

  vector<map<PII, bool>> there(n);

  for (int i = 1; i < n - 1; i++) {
    trav(x, pos[i]) there[i][x] = true;
  }

  // deb(prv);
  // deb(nxt);

  ll ret = 0;

  // const PII bad1 = MP(2, 4);
  // const int bad2 = 3;

  // timeit log("finding rectangles");

  mx = 0;

  for (int i = 1; i < n - 1; i++) {
    timeit fori("for a single i");
    int cnt = 0;
    for (auto& x : pos[i]) {
      // debug(i, x);
      int e = i;
      if (there[i][x] == false) continue;
      for (int j = i; j < n - 1; j++) {
        cnt++;
        // if (x == bad1 and i == bad2) debug("here1", x, i, j);
        if (there[j][x] == false) break;
        // if (x == bad1 and i == bad2) debug("here", x, i, j);
        there[j][x] = false;
        e = j;
      }
      ll cur = solve(x.x, x.y, i, e);
      ret += cur;
      // if (cur > 0) debug(cur, x.x, x.y, i, e);
    }
    fori.stop();
    debug(cnt);
    mx = max(mx, cnt);
    // debug(sz(pos[i]));
  }

  debug(mx);
  if (n > 100) trav(x, pos[n - 3]) debug(x);
  if (n > 100) debug(sz(pos[n - 3]));
  // log.stop();

  const int bad = 3;

  // spmn[bad].deb();
  // debug(spmn[bad].qry(2, 3));
  // slv.stop();
  return ret;
}

Compilation message (stderr)

rect.cpp: In member function 'void timeit::stop()':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:66:5: note: in expansion of macro 'debug'
   66 |     debug(dur.str());
      |     ^~~~~
rect.cpp: In function 'void deb(VVI&)':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:80:3: note: in expansion of macro 'debug'
   80 |   debug("debugging");
      |   ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:81:14: note: in expansion of macro 'debug'
   81 |   trav(x, a) debug(x);
      |              ^~~~~
rect.cpp:31:11: warning: unused variable 'first' [-Wunused-variable]
   31 | #define x first
      |           ^~~~~
rect.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
rect.cpp:81:8: note: in expansion of macro 'x'
   81 |   trav(x, a) debug(x);
      |        ^
rect.cpp: In member function 'void sptable::deb()':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:155:29: note: in expansion of macro 'debug'
  155 |   void deb() { trav(x, spt) debug(x); }
      |                             ^~~~~
rect.cpp:31:11: warning: unused variable 'first' [-Wunused-variable]
   31 | #define x first
      |           ^~~~~
rect.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
rect.cpp:155:21: note: in expansion of macro 'x'
  155 |   void deb() { trav(x, spt) debug(x); }
      |                     ^
rect.cpp: In function 'll solvesub6(VVI&)':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:325:9: note: in expansion of macro 'debug'
  325 |         debug(p1);
      |         ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:335:9: note: in expansion of macro 'debug'
  335 |         debug(p2);
      |         ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:338:7: note: in expansion of macro 'debug'
  338 |       debug(i, j, p1, p2);
      |       ^~~~~
rect.cpp: In function 'll count_rectangles(VVI)':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:484:5: note: in expansion of macro 'debug'
  484 |     debug(cnt);
      |     ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:489:3: note: in expansion of macro 'debug'
  489 |   debug(mx);
      |   ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:490:36: note: in expansion of macro 'debug'
  490 |   if (n > 100) trav(x, pos[n - 3]) debug(x);
      |                                    ^~~~~
rect.cpp:31:11: warning: unused variable 'first' [-Wunused-variable]
   31 | #define x first
      |           ^~~~~
rect.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
rect.cpp:490:21: note: in expansion of macro 'x'
  490 |   if (n > 100) trav(x, pos[n - 3]) debug(x);
      |                     ^
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:491:16: note: in expansion of macro 'debug'
  491 |   if (n > 100) debug(sz(pos[n - 3]));
      |                ^~~~~
rect.cpp:494:13: warning: unused variable 'bad' [-Wunused-variable]
  494 |   const int bad = 3;
      |             ^~~

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