Submission #423358

#	Time	Username	Problem	Language	Result	Execution time	Memory
423358		79brue	Rectangles (IOI19_rect)	C++14	100 / 100	4204 ms	955200 KiB

rect

#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); /// 간단한 초기화를 합니다.
	M = N = max(N, M);
	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<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{
            assert(*it1 == *it2);
            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: 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