## Submission #423352

# Submission time Handle Problem Language Result Execution time Memory
423352 2021-06-11T02:39:28 Z 79brue Rectangles (IOI19_rect) C++14
0 / 100
1332 ms 1048580 KB
```#include <bits/stdc++.h>
#define LIM 2502
#include "rect.h"

using namespace std;

typedef long long ll;

int N, M;
int arr[LIM][LIM];
int power2[LIM];
int columnDncLoc[LIM][LIM];
ll ans;

short maxLeft[LIM][LIM][11], maxRight[LIM][LIM][11];
short maxUp[LIM][LIM][11], maxDown[LIM][LIM][11];

vector<pair<short, short> > rangeRow, rangeColumn[LIM][LIM];

void init(vector<vector<int> > &);
void makeColumnDncLoc(int, int);
void makeSparse();
void findRange();

void divideAndConquer(int, int);

ll count_rectangles(vector<vector<int> > a) {
init(a); /// 간단한 초기화를 합니다.
makeColumnDncLoc(2, N-1);
makeSparse(); /// 행 / 열 구간 최댓값의 위치를 찾기 위해 스파스 테이블을 만듭니다.
findRange(); /// 각 행/열에 대해 카르테시안 트리를 만듭니다.
divideAndConquer(2, N-1);
return ans;
}

void init(vector<vector<int> > &a){
N = a.size(); M = a[0].size();
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
arr[i+1][j+1] = a[i][j];
}
}

for(int i=0; i<=2500; i++){
for(int d=1; d<12; d++){
if((1<<d) > i+1){
power2[i] = d-1;
break;
}
}
}
}

void makeColumnDncLoc(int l, int r){
if(l>r) return;
int m = (l+r)>>1;
for(int i=l; i<=m; i++){
for(int j=m; j<=r; j++){
columnDncLoc[i][j] = m;
}
}
makeColumnDncLoc(l, m-1);
makeColumnDncLoc(m+1, r);
}

void makeSparse(){
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
maxLeft[i][j][0] = maxRight[i][j][0] = j;
maxUp[i][j][0] = maxDown[i][j][0] = i;
}
}

for(int d=1; d<11; d++){
int v = (1<<(d-1));
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
if(j>v){
if(arr[i][maxLeft[i][j][d-1]] > arr[i][maxLeft[i][j-v][d-1]]) maxLeft[i][j][d] = maxLeft[i][j][d-1];
else maxLeft[i][j][d] = maxLeft[i][j-v][d-1];
}
if(j+v<=M){
if(arr[i][maxRight[i][j][d-1]] > arr[i][maxRight[i][j+v][d-1]]) maxRight[i][j][d] = maxRight[i][j][d-1];
else maxRight[i][j][d] = maxRight[i][j+v][d-1];
}
if(i>v){
if(arr[maxUp[i][j][d-1]][j] > arr[maxUp[i-v][j][d-1]][j]) maxUp[i][j][d] = maxUp[i][j][d-1];
else maxUp[i][j][d] = maxUp[i-v][j][d-1];
}
if(i+v<=M){
if(arr[maxDown[i][j][d-1]][j] > arr[maxDown[i+v][j][d-1]][j]) maxDown[i][j][d] = maxDown[i][j][d-1];
else maxDown[i][j][d] = maxDown[i+v][j][d-1];
}
}
}
}
}

short rowMax(int i, int l, int r){
short cand1 = maxRight[i][l][power2[r-l]];
short cand2 = maxLeft[i][r][power2[r-l]];
return arr[i][cand1] > arr[i][cand2] ? cand1 : cand2;
}

short columnMax(int i, int l, int r){
short cand1 = maxDown[l][i][power2[r-l]];
short cand2 = maxUp[r][i][power2[r-l]];
return arr[cand1][i] > arr[cand2][i] ? cand1 : cand2;
}

void findRangeRow(int i, int l, int r){
if(l==r){
rangeRow.push_back(make_pair(l, r));
return;
}
int m = rowMax(i, l, r);
if(m!=l) findRangeRow(i, l, m-1);
if(m!=r) findRangeRow(i, m+1, r);
rangeRow.push_back(make_pair(l, r));
}

void findRangeColumn(int i, int l, int r){
if(l==r){
if(arr[l][i] < min(arr[l-1][i], arr[r+1][i])){
rangeColumn[i][columnDncLoc[l][r]].push_back(make_pair(l, r));
}
return;
}
int m = columnMax(i, l, r);
if(m!=l) findRangeColumn(i, l, m-1);
if(m!=r) findRangeColumn(i, m+1, r);
if(arr[columnMax(i, l, r)][i] < min(arr[l-1][i], arr[r+1][i])){
rangeColumn[i][columnDncLoc[l][r]].push_back(make_pair(l, r));
}
}

inline bool cmp(pair<short, short> it1, pair<short, short> it2){
if(it1.second != it2.second) return it1.second < it2.second;
return it1.first > it2.first;
}

void findRange(){
for(int i=2; i<M; i++){
findRangeColumn(i, 2, N-1);
}
}

vector<pair<short, short> > vec[LIM]; /// 각 열별로 가능한 위/아래 후보에 관한 정보를 담고 있게 될 벡터입니다.
vector<pair<short, short> > ret;

void mergeVec(int l, int r){
for(auto it1 = vec[l].begin(), it2 = vec[r].begin(); it1 != vec[l].end() && it2 != vec[r].end(); ){
if(cmp(*it1, *it2)) ++it1;
else if(cmp(*it2, *it1)) ++it2;
else{
ret.push_back(*it1);
++it1;
++it2;
}
}
vec[l].swap(ret);
vec[r].clear();
vec[r].shrink_to_fit();
ret.clear();
ret.shrink_to_fit();
}

void divideAndConquer(int l, int r){
if(l>r) return;
int m = (l+r)>>1;

for(int i=2; i<M; i++){ /// vec 벡터를 전처리합니다.
vec[i].swap(rangeColumn[i][m]);
rangeColumn[i][m].clear();
rangeColumn[i][m].shrink_to_fit();
}

rangeRow.clear();
findRangeRow(m, 2, M-1);
for(auto _pair: rangeRow){ /// m번 행이 무조건 포함된다고 고정하고, 가능한 (왼쪽 경계, 오른쪽 경계) 쌍을 시도합니다.
int s = _pair.first, e = _pair.second; /// 왼쪽 경계와 오른쪽 경계입니다.
int tl = m, tr = m; /// 이 두 변수는 가능한 위쪽 한계 / 아래쪽 한계를 담당합니다.

while(tl > l){
if(arr[tl-1][rowMax(tl-1, s, e)] < min(arr[tl-1][s-1], arr[tl-1][e+1])) tl--;
else break;
}
while(tr < r){
if(arr[tr+1][rowMax(tr+1, s, e)] < min(arr[tr+1][s-1], arr[tr+1][e+1])) tr++;
else break;
}

if(s != e){
int mid = rowMax(m, s, e);
if(mid != s) mergeVec(s, mid);
if(mid != e) mergeVec(s, mid+1);
}

if(arr[m][rowMax(m, s, e)] >= min(arr[m][s-1], arr[m][e+1])) continue;
for(auto p: vec[s]){
if(tl <= p.first && p.second <= tr) ans++;
}
}

divideAndConquer(l, m-1);
divideAndConquer(m+1, r);
}
```

#### Subtask #1 0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 147480 KB Output is correct
2 Correct 98 ms 148284 KB Output is correct
3 Correct 92 ms 148108 KB Output is correct
4 Correct 103 ms 148156 KB Output is correct
5 Correct 93 ms 148164 KB Output is correct
6 Correct 92 ms 148116 KB Output is correct
7 Incorrect 90 ms 148036 KB Output isn't correct
8 Halted 0 ms 0 KB -

#### Subtask #2 0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 147480 KB Output is correct
2 Correct 98 ms 148284 KB Output is correct
3 Correct 92 ms 148108 KB Output is correct
4 Correct 103 ms 148156 KB Output is correct
5 Correct 93 ms 148164 KB Output is correct
6 Correct 92 ms 148116 KB Output is correct
7 Incorrect 90 ms 148036 KB Output isn't correct
8 Halted 0 ms 0 KB -

#### Subtask #3 0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 147480 KB Output is correct
2 Correct 98 ms 148284 KB Output is correct
3 Correct 92 ms 148108 KB Output is correct
4 Correct 103 ms 148156 KB Output is correct
5 Correct 93 ms 148164 KB Output is correct
6 Correct 92 ms 148116 KB Output is correct
7 Incorrect 90 ms 148036 KB Output isn't correct
8 Halted 0 ms 0 KB -

#### Subtask #4 0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 147480 KB Output is correct
2 Correct 98 ms 148284 KB Output is correct
3 Correct 92 ms 148108 KB Output is correct
4 Correct 103 ms 148156 KB Output is correct
5 Correct 93 ms 148164 KB Output is correct
6 Correct 92 ms 148116 KB Output is correct
7 Incorrect 90 ms 148036 KB Output isn't correct
8 Halted 0 ms 0 KB -

#### Subtask #5 0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 148316 KB Output is correct
2 Correct 93 ms 148184 KB Output is correct
3 Correct 98 ms 148188 KB Output is correct
4 Runtime error 605 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

#### Subtask #6 0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 147528 KB Output is correct
2 Incorrect 1332 ms 478132 KB Output isn't correct
3 Halted 0 ms 0 KB -

#### Subtask #7 0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 147480 KB Output is correct
2 Correct 98 ms 148284 KB Output is correct
3 Correct 92 ms 148108 KB Output is correct
4 Correct 103 ms 148156 KB Output is correct
5 Correct 93 ms 148164 KB Output is correct
6 Correct 92 ms 148116 KB Output is correct
7 Incorrect 90 ms 148036 KB Output isn't correct
8 Halted 0 ms 0 KB -