제출 #296672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296672		ChrisT	Rectangles (IOI19_rect)	C++17	100 / 100	2883 ms	378964 KiB

rect

#include <bits/stdc++.h> 
#include "rect.h"
using namespace std; 
inline long long hsh (int a, int b, int c, int d) {
  return ((long long)a << 36) | ((long long)b << 24) | ((long long)c << 12) | ((long long)d);
}
long long count_rectangles (vector<vector<int>> a) {
  int n = a.size(), m = a[0].size();
  vector<vector<int>> nextLeft(n,vector<int>(m,1e9)), nextRight(n,vector<int>(m,-1)), nextUp(n,vector<int>(m,1e9)), nextDown(n,vector<int>(m,-1)), upFromLeft(n,vector<int>(m)),upFromRight(n,vector<int>(m)),leftFromDown(n,vector<int>(m)),leftFromUp(n,vector<int>(m));
  for (int i = 0; i < n; i++) {
    vector<int> stk;
    for (int j = 0; j < m; j++) {
      while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
      if (!stk.empty()) {
        nextLeft[i][j] = stk.back();
        upFromLeft[i][j] = 1;
        if (i > 0 && nextLeft[i-1][j] == nextLeft[i][j]) upFromLeft[i][j] += upFromLeft[i-1][j];
        else if (i > 0 && nextRight[i-1][stk.back()] == j) upFromLeft[i][j] += upFromRight[i-1][stk.back()];
      }
      stk.push_back(j);
    }
    stk.clear();
    for (int j = m-1; j >= 0; j--) {
      while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
      if (!stk.empty()) {
        nextRight[i][j] = stk.back();
        upFromRight[i][j] = 1;
        if (i > 0 && nextRight[i-1][j] == nextRight[i][j]) upFromRight[i][j] += upFromRight[i-1][j];
        else if (i > 0 && nextLeft[i-1][stk.back()] == j) upFromRight[i][j] += upFromLeft[i-1][stk.back()];
      }
      stk.push_back(j);
    }
  }
  for (int j = 0; j < m; j++) {
    vector<int> stk;
    for (int i = 0; i < n; i++) {
      while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
      if (!stk.empty()) {
        nextUp[i][j] = stk.back();
        leftFromUp[i][j] = 1;
        if (j > 0 && nextUp[i][j-1] == nextUp[i][j]) leftFromUp[i][j] += leftFromUp[i][j-1];
        else if (j > 0 && nextDown[stk.back()][j-1] == i) leftFromUp[i][j] += leftFromDown[stk.back()][j-1];
      }
      stk.push_back(i);
    }
    stk.clear();
    for (int i = n-1; i >= 0; i--) {
      while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
      if (!stk.empty()) {
        nextDown[i][j] = stk.back();
        leftFromDown[i][j] = 1;
        if (j > 0 && nextDown[i][j-1] == nextDown[i][j]) leftFromDown[i][j] += leftFromDown[i][j-1];
        else if (j > 0 && nextUp[stk.back()][j-1] == i) leftFromDown[i][j] += leftFromUp[stk.back()][j-1];
      }
      stk.push_back(i);
    }
  }
  auto works = [&] (int bx, int ry, int tx, int ly) {
    return ((nextLeft[bx-1][ry] == ly && bx - upFromLeft[bx-1][ry] <= tx + 1) || (nextRight[bx-1][ly] == ry && bx - upFromRight[bx-1][ly] <= tx + 1)) && ((nextUp[bx][ry-1] == tx && ry - leftFromUp[bx][ry-1] <= ly + 1) || (nextDown[tx][ry-1] == bx && ry - leftFromDown[tx][ry-1] <= ly + 1));
  };
  auto ok = [&] (int x) {return x >= 0 && x < n;};
  vector<long long> can;
  auto go = [&] (int i, int j, int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || abs(i-x) <= 1 || abs(j-y) <= 1) return;
    if (x < i) swap(x,i);
    if (y < j) swap(y,j);
    if (works(x,y,i,j)) can.push_back(hsh(i,j,x,y));
  };
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i > 0 && j > 0 && ok(nextUp[i][j-1])) go(i,j,nextUp[i][j-1],nextLeft[i-1][j]), go(i,j,nextUp[i][j-1],nextLeft[nextUp[i][j-1]+1][j]);
      if (i > 0 && j+1 < m && ok(nextUp[i][j+1])) go(i,j,nextUp[i][j+1],nextRight[i-1][j]), go(i,j,nextUp[i][j+1],nextRight[nextUp[i][j+1]+1][j]);
      if (i+1 < n && j > 0 && ok(nextDown[i][j-1])) go(i,j,nextDown[i][j-1],nextLeft[i+1][j]), go(i,j,nextDown[i][j-1],nextLeft[nextDown[i][j-1]-1][j]);
      if (i+1 < n && j+1 < m && ok(nextDown[i][j+1])) go(i,j,nextDown[i][j+1],nextRight[i+1][j]), go(i,j,nextDown[i][j+1],nextRight[nextDown[i][j+1]-1][j]);
    }
  }
  sort(can.begin(),can.end()); 
  return unique(can.begin(),can.end()) - can.begin();
}

• 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