제출 #328770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
328770		VROOM_VARUN	Rectangles (IOI19_rect)	C++17	10 / 100	3740 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

int n, m;

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) {
    if (r < l) return 0;
    return qry(r) - qry(l - 1);
  }
};

struct sptable {
  const int bits = 13;
  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]) {
        ret.PB(MP(ind, i));
        break;
      } else {
        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;
  // 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) {
      fen.upd(val - 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);
    }
  }

  // debug(sweep);
  // debug(l, r, s, e);
  // debug(ret);

  return ret;
}

ll count_rectangles(VVI a) {
  n = sz(a);
  m = sz(a[0]);
  init(a);
  vector<VII> pos(n);
  for (int i = 0; i < n; i++) {
    pos[i] = gen(grid[i]);
  }

  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);
  }

  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;

  for (int i = 1; i < n - 1; i++) {
    for (auto& x : pos[i]) {
      // debug(i, x);
      int e;
      if (there[i][x] == false) continue;
      for (int j = i; j < n - 1; j++) {
        // 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);
    }
  }

  const int bad = 3;

  // spmn[bad].deb();
  // debug(spmn[bad].qry(2, 3));

  return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'void deb(VVI&)':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:63:3: note: in expansion of macro 'debug'
   63 |   debug("debugging");
      |   ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:64:14: note: in expansion of macro 'debug'
   64 |   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:64:8: note: in expansion of macro 'x'
   64 |   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:136:29: note: in expansion of macro 'debug'
  136 |   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:136:21: note: in expansion of macro 'x'
  136 |   void deb() { trav(x, spt) debug(x); }
      |                     ^
rect.cpp: In function 'll count_rectangles(VVI)':
rect.cpp:314:13: warning: unused variable 'bad' [-Wunused-variable]
  314 |   const int bad = 3;
      |             ^~~
rect.cpp:308:21: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  308 |       ll cur = solve(x.x, x.y, i, e);
      |                ~~~~~^~~~~~~~~~~~~~~~

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