Submission #899738

#	Time	Username	Problem	Language	Result	Execution time	Memory
899738		rxlfd314	Rectangles (IOI19_rect)	C++17	50 / 100	5095 ms	208596 KiB

rect

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

struct BIT {
  vt<int> fen;
  BIT(int n) {
    fen.resize(n);
  }
  void upd(int i, int v) {
    for (; i < size(fen); i += i+1 & -i-1)
      fen[i] += v;
  }
  int qry(int i) {
    int ret = 0;
    for (; i >= 0; i -= i+1 & -i-1)
      ret += fen[i];
    return ret;
  }
  int qry(int l, int r) {
    return r < l ? 0 : qry(r) - qry(l-1);
  }
};

ll ST1(vt<vt<int>> A) {
  const int N = size(A), M = size(A[0]);
  int psum[N][M], U[N][M], L[N][M], L2[N][M], U2[N][M];
  memset(L, 0x3f, sizeof(L));
  memset(U, 0x3f, sizeof(U));
  memset(L2, 0x3f, sizeof(L2));
  memset(U2, 0x3f, sizeof(U2));
  ll ans = 0;
  FOR(i, 1, N-2)
    FOR(j, 1, M-2) {
      psum[i][j] = A[i][j] + (i ? psum[i-1][j] : 0) + (j ? psum[i][j-1] : 0) - (i && j ? psum[i-1][j-1] : 0);
      U[i][j] = A[i][j] < A[i][j+1] ? min(i, U[i-1][j]) : INT_MAX;
      L[i][j] = A[i][j] < A[i+1][j] ? min(j, L[i][j-1]) : INT_MAX;
      U2[i][j] = A[i][j] < A[i][j-1] ? min(i, U2[i-1][j]) : INT_MAX;
      L2[i][j] = A[i][j] < A[i-1][j] ? min(j, L2[i][j-1]) : INT_MAX;
      ans += L[i][j] <= j && U[i][j] <= i && L2[U[i][j]][j] == L[i][j] && U2[i][L[i][j]] == U[i][j] && L[i][j] && U[i][j] && psum[i][j] - psum[U[i][j]-1][j] - psum[i][L[i][j]-1] + psum[U[i][j]-1][L[i][j]-1] == 0;
    }
  return ans;
}

ll count_rectangles(vt<vt<int>> A) {
  const int N = size(A), M = size(A[0]);
  bool sub1 = true;
  FOR(i, 0, N-1)
    FOR(j, 0, M-1)
      sub1 &= A[i][j] < 2;
  if (sub1)
    return ST1(A);
  int X[N][M], Y[N][M];
  FOR(i, 0, N-1) {
    vt<int> sk;
    FOR(j, 0, M-1) {
      while (size(sk) && A[i][sk.back()] < A[i][j])
        sk.pop_back();
      X[i][j] = size(sk) ? sk.back() + 1 : 0;
      sk.push_back(j);
    }
    sk.clear();
    ROF(j, M-1, 0) {
      while (size(sk) && A[i][sk.back()] < A[i][j])
        sk.pop_back();
      Y[i][j] = size(sk) ? sk.back() - 1 : M - 1;
      sk.push_back(j);
    }
  }
  #ifdef DEBUG
  cout << "X:\n";
  FOR(i, 0, N-1)
    FOR(j, 0, M-1)
      cout << X[i][j] << "\n "[j+1<M];
  cout << "Y:\n";
  FOR(i, 0, N-1)
    FOR(j, 0, M-1)
      cout << Y[i][j] << "\n "[j+1<M];
  #endif
  
  ll ans = 0;
  int R[M], L[M], mx[M];
  FOR(l, 1, N-2) {
    memset(R, 0x3f, sizeof(R));
    memset(L, 0xc0, sizeof(L));
    memset(mx, 0xc0, sizeof(mx));
    FOR(r, l, N-2) {
      FOR(i, 0, M-1) {
        R[i] = min(R[i], Y[r][i]);
      }
      int ord[M];
      iota(ord, ord+M, 0);
      sort(ord, ord+M, [&](const int &a, const int &b) {
        return R[a] < R[b];    
      });
      BIT fen(M);
      priority_queue<ari2, vt<ari2>, greater<ari2>> ma;
      int dead_bef = 0, j = 0, k = 0;
      bool dead[M] = {};
      FOR(i, 0, M-1) {
        for (; k < M && R[ord[k]] < i-1; k++)
          if (!dead[ord[k]]) {
            dead[ord[k]] = true;
            fen.upd(ord[k], -1);
          }
        for (; j < dead_bef; j++)
          if (!dead[j]) {
            fen.upd(j, -1);
            dead[j] = true;
          }
        R[i] = min(R[i], Y[r][i]);
        L[i] = max(L[i], X[r][i]);
        mx[i] = max(mx[i], A[r][i]);
        if (i && mx[i-1] < min(A[l-1][i-1], A[r+1][i-1])) {
          ans += fen.qry(L[i]-1, i-2);
#ifdef DEBUG
          cout << "contribution from " << i-1 << ' ' << l << ' ' << r << ": " << fen.qry(L[i]-1, i-2) << '\n';
#endif
        } else {
          dead_bef = i - 1;
        }
        ma.push({R[i], i});
        fen.upd(i, 1);
      }
    }
  }
  return ans;
}

Compilation message (stderr)

rect.cpp: In member function 'void BIT::upd(int, int)':
rect.cpp:23:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   23 |     for (; i < size(fen); i += i+1 & -i-1)
      |                                ~^~
rect.cpp: In member function 'int BIT::qry(int)':
rect.cpp:28:26: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   28 |     for (; i >= 0; i -= i+1 & -i-1)
      |                         ~^~

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