# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
423350 |
2021-06-11T02:36:00 Z |
79brue |
Rectangles (IOI19_rect) |
C++14 |
|
1093 ms |
501176 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][12], maxRight[LIM][LIM][12];
short maxUp[LIM][LIM][12], maxDown[LIM][LIM][12];
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(); /// 각 행/열에 대해 카르테시안 트리를 만듭니다.
if(N>2000 || M>2000) return ans;
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<20; 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<12; 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);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
147608 KB |
Output is correct |
2 |
Correct |
98 ms |
148180 KB |
Output is correct |
3 |
Correct |
95 ms |
148096 KB |
Output is correct |
4 |
Correct |
92 ms |
148092 KB |
Output is correct |
5 |
Correct |
99 ms |
148088 KB |
Output is correct |
6 |
Correct |
93 ms |
148092 KB |
Output is correct |
7 |
Incorrect |
96 ms |
148060 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
147608 KB |
Output is correct |
2 |
Correct |
98 ms |
148180 KB |
Output is correct |
3 |
Correct |
95 ms |
148096 KB |
Output is correct |
4 |
Correct |
92 ms |
148092 KB |
Output is correct |
5 |
Correct |
99 ms |
148088 KB |
Output is correct |
6 |
Correct |
93 ms |
148092 KB |
Output is correct |
7 |
Incorrect |
96 ms |
148060 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
147608 KB |
Output is correct |
2 |
Correct |
98 ms |
148180 KB |
Output is correct |
3 |
Correct |
95 ms |
148096 KB |
Output is correct |
4 |
Correct |
92 ms |
148092 KB |
Output is correct |
5 |
Correct |
99 ms |
148088 KB |
Output is correct |
6 |
Correct |
93 ms |
148092 KB |
Output is correct |
7 |
Incorrect |
96 ms |
148060 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
147608 KB |
Output is correct |
2 |
Correct |
98 ms |
148180 KB |
Output is correct |
3 |
Correct |
95 ms |
148096 KB |
Output is correct |
4 |
Correct |
92 ms |
148092 KB |
Output is correct |
5 |
Correct |
99 ms |
148088 KB |
Output is correct |
6 |
Correct |
93 ms |
148092 KB |
Output is correct |
7 |
Incorrect |
96 ms |
148060 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
93 ms |
148184 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
147524 KB |
Output is correct |
2 |
Incorrect |
1093 ms |
501176 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
147608 KB |
Output is correct |
2 |
Correct |
98 ms |
148180 KB |
Output is correct |
3 |
Correct |
95 ms |
148096 KB |
Output is correct |
4 |
Correct |
92 ms |
148092 KB |
Output is correct |
5 |
Correct |
99 ms |
148088 KB |
Output is correct |
6 |
Correct |
93 ms |
148092 KB |
Output is correct |
7 |
Incorrect |
96 ms |
148060 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |