Submission #899473

#	Time	Username	Problem	Language	Result	Execution time	Memory
899473		rxlfd314	Rectangles (IOI19_rect)	C++17	37 / 100	5060 ms	48400 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 count_rectangles(vt<vt<int>> A) {
  const int N = size(A), M = size(A[0]);
  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) {
      BIT fen(M);
      multiset<ari2> ma;
      multiset<int> mb;
      int dead_bef = 0;
      FOR(i, 0, M-1) {
        while (size(ma)) {
          auto [a, b] = *begin(ma);
          if (a >= i-1)
            break;
          ma.erase(begin(ma));
          mb.erase(mb.find(b));
          fen.upd(b, -1);
        }
        while (size(mb)) {
          int a = *begin(mb);
          if (a >= dead_bef)
            break;
          mb.erase(begin(mb));
          ma.erase(ma.find({R[a], a}));
          fen.upd(a, -1);
        }
        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.insert({R[i], i});
        mb.insert(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: 0 / 13
• Subtask 7: 0 / 28