제출 #1312061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312061		altern23	Rectangles (IOI19_rect)	C++20	100 / 100	1857 ms	624984 KiB

rect

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

#define ll int
#define fi first
#define sec second

ll bit[2505];
ll N, M;

void upd(ll idx, ll val) {
  for (; idx <= M; idx += idx & -idx) bit[idx] += val;
}

ll get(ll idx) {
  ll ans = 0;
  for (; idx >= 1; idx -= idx & -idx) ans += bit[idx];
  return ans;
}

ll query(ll l, ll r) {
  return get(r) - get(l - 1);
}

long long count_rectangles(vector<vector<int>> a) {
  N = a.size();
  M = a[0].size();
    
  pair<ll, ll> lst[max(N, M) + 1][max(N, M)];
  
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      lst[i][j] = {0, -1};
    }
  }
  
  vector <pair<ll, ll>> h[N][M], v[N][M];
  
  for (int i = 0; i < N; i++) {
    stack <ll> stk;
    for (int j = 0; j < M; j++) {
      bool sm = 0;
      while (!stk.empty() && a[i][stk.top()] <= a[i][j]) {
            sm |= (a[i][stk.top()] == a[i][j]);
        if (j - stk.top() >= 2) {
          ll sz;
          if (lst[stk.top()][j].sec != i - 1) {
            sz = 1;
          }
          else {
            sz = lst[stk.top()][j].fi + 1;
          }
          lst[stk.top()][j] = {sz, i};
          h[i][j].push_back({sz, j - stk.top() - 1});
        }
        stk.pop();
      }
      if (!stk.empty() && !sm) {
        if (j - stk.top() >= 2) {
          ll sz;
          if (lst[stk.top()][j].sec != i - 1) {
            sz = 1;
          }
          else {
            sz = lst[stk.top()][j].fi + 1;
          }
          lst[stk.top()][j] = {sz, i};
          h[i][j].push_back({sz, j - stk.top() - 1});
        }
      }
      sort(h[i][j].begin(), h[i][j].end());
      stk.push(j);
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      lst[i][j] = {0, -1};
    }
  }
  
  for (int j = 0; j < M; j++) {
    stack <ll> stk;
    for (int i = 0; i < N; i++) {
      bool sm = 0;
      while (!stk.empty() && a[stk.top()][j] <= a[i][j]) {
            sm |= (a[stk.top()][j] == a[i][j]);
        if (i - stk.top() >= 2) {
          ll sz;
          if (lst[stk.top()][i].sec != j - 1) {
            sz = 1;
          }
          else {
            sz = lst[stk.top()][i].fi + 1;
          }
          lst[stk.top()][i] = {sz, j};
          v[i][j].push_back({i - stk.top() - 1, sz});
        }
        stk.pop();
      }
      if (!stk.empty() && !sm) {
        if (i - stk.top() >= 2) {
          ll sz;
          if (lst[stk.top()][i].sec != j - 1) {
            sz = 1;
          }
          else {
            sz = lst[stk.top()][i].fi + 1;
          }
          lst[stk.top()][i] = {sz, j};
          v[i][j].push_back({i - stk.top() - 1, sz});
        }
      }
      sort(v[i][j].begin(), v[i][j].end());
      // cout << i << " " << j << "\n";
      // for (auto [x, y] : v[i][j]) cout << x << " " << y << "\n";
      // cout << "\n";
      stk.push(i);
    }
  }
  
  /*
  H -> {b, a}
  V -> {c, d}
  b >= c
  d >= a
  */
    
  ll ans = 0;
  for (int i = 0; i < N - 1; i++) {
    for (int j = 1; j < M; j++) {
      ll pt = -1;
      for (auto [b, a] : h[i][j]) {
        while (pt + 1 < (ll)v[i + 1][j - 1].size()) {
          auto [c, d] = v[i + 1][j - 1][pt + 1];
          if (b >= c) {
            upd(d, 1);
            pt++;
          }
          else {
            break;
          }
        }
        ans += query(a, M);
      }
      for (int k = 0; k <= pt; k++) {
        auto [c, d] = v[i + 1][j - 1][k];
        upd(d, -1);
      }
    }
  }
  
  return ans;
}

• 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: 28 / 28