oj.uz

Submission #423358

# Submission time Handle Problem Language Result Execution time Memory
423358 2021-06-11T02:46:32 Z 79brue Rectangles (IOI19_rect) C++14
100 / 100
 4204 ms 955200 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); /// 간단한 초기화를 합니다.
	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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 147520 KB Output is correct
2 Correct 79 ms 148124 KB Output is correct
3 Correct 84 ms 148200 KB Output is correct
4 Correct 91 ms 148244 KB Output is correct
5 Correct 79 ms 148188 KB Output is correct
6 Correct 80 ms 148084 KB Output is correct
7 Correct 80 ms 148100 KB Output is correct
8 Correct 89 ms 148076 KB Output is correct
9 Correct 80 ms 148088 KB Output is correct
10 Correct 79 ms 148180 KB Output is correct
11 Correct 81 ms 148128 KB Output is correct
12 Correct 87 ms 148164 KB Output is correct
13 Correct 81 ms 147396 KB Output is correct
14 Correct 80 ms 147504 KB Output is correct
15 Correct 82 ms 147596 KB Output is correct
16 Correct 80 ms 147396 KB Output is correct
17 Correct 79 ms 147372 KB Output is correct
18 Correct 79 ms 147388 KB Output is correct
19 Correct 78 ms 148140 KB Output is correct
20 Correct 81 ms 148076 KB Output is correct
21 Correct 91 ms 147524 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 147520 KB Output is correct
2 Correct 79 ms 148124 KB Output is correct
3 Correct 84 ms 148200 KB Output is correct
4 Correct 91 ms 148244 KB Output is correct
5 Correct 79 ms 148188 KB Output is correct
6 Correct 80 ms 148084 KB Output is correct
7 Correct 80 ms 148100 KB Output is correct
8 Correct 89 ms 148076 KB Output is correct
9 Correct 80 ms 148088 KB Output is correct
10 Correct 79 ms 148180 KB Output is correct
11 Correct 81 ms 148128 KB Output is correct
12 Correct 87 ms 148164 KB Output is correct
13 Correct 81 ms 147396 KB Output is correct
14 Correct 80 ms 147504 KB Output is correct
15 Correct 82 ms 147596 KB Output is correct
16 Correct 80 ms 147396 KB Output is correct
17 Correct 79 ms 147372 KB Output is correct
18 Correct 79 ms 147388 KB Output is correct
19 Correct 78 ms 148140 KB Output is correct
20 Correct 81 ms 148076 KB Output is correct
21 Correct 91 ms 147524 KB Output is correct
22 Correct 82 ms 150052 KB Output is correct
23 Correct 82 ms 150072 KB Output is correct
24 Correct 82 ms 150084 KB Output is correct
25 Correct 80 ms 150076 KB Output is correct
26 Correct 83 ms 150076 KB Output is correct
27 Correct 85 ms 150068 KB Output is correct
28 Correct 80 ms 150008 KB Output is correct
29 Correct 80 ms 149936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 147520 KB Output is correct
2 Correct 79 ms 148124 KB Output is correct
3 Correct 84 ms 148200 KB Output is correct
4 Correct 91 ms 148244 KB Output is correct
5 Correct 79 ms 148188 KB Output is correct
6 Correct 80 ms 148084 KB Output is correct
7 Correct 80 ms 148100 KB Output is correct
8 Correct 89 ms 148076 KB Output is correct
9 Correct 80 ms 148088 KB Output is correct
10 Correct 79 ms 148180 KB Output is correct
11 Correct 81 ms 148128 KB Output is correct
12 Correct 87 ms 148164 KB Output is correct
13 Correct 81 ms 147396 KB Output is correct
14 Correct 80 ms 147504 KB Output is correct
15 Correct 82 ms 147596 KB Output is correct
16 Correct 80 ms 147396 KB Output is correct
17 Correct 82 ms 150052 KB Output is correct
18 Correct 82 ms 150072 KB Output is correct
19 Correct 82 ms 150084 KB Output is correct
20 Correct 80 ms 150076 KB Output is correct
21 Correct 83 ms 150076 KB Output is correct
22 Correct 85 ms 150068 KB Output is correct
23 Correct 80 ms 150008 KB Output is correct
24 Correct 80 ms 149936 KB Output is correct
25 Correct 79 ms 147372 KB Output is correct
26 Correct 79 ms 147388 KB Output is correct
27 Correct 78 ms 148140 KB Output is correct
28 Correct 81 ms 148076 KB Output is correct
29 Correct 91 ms 147524 KB Output is correct
30 Correct 109 ms 156964 KB Output is correct
31 Correct 107 ms 157028 KB Output is correct
32 Correct 95 ms 157120 KB Output is correct
33 Correct 92 ms 157016 KB Output is correct
34 Correct 95 ms 157344 KB Output is correct
35 Correct 98 ms 157472 KB Output is correct
36 Correct 99 ms 157360 KB Output is correct
37 Correct 94 ms 157372 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 147520 KB Output is correct
2 Correct 79 ms 148124 KB Output is correct
3 Correct 84 ms 148200 KB Output is correct
4 Correct 91 ms 148244 KB Output is correct
5 Correct 79 ms 148188 KB Output is correct
6 Correct 80 ms 148084 KB Output is correct
7 Correct 80 ms 148100 KB Output is correct
8 Correct 89 ms 148076 KB Output is correct
9 Correct 80 ms 148088 KB Output is correct
10 Correct 79 ms 148180 KB Output is correct
11 Correct 81 ms 148128 KB Output is correct
12 Correct 87 ms 148164 KB Output is correct
13 Correct 81 ms 147396 KB Output is correct
14 Correct 80 ms 147504 KB Output is correct
15 Correct 82 ms 147596 KB Output is correct
16 Correct 80 ms 147396 KB Output is correct
17 Correct 82 ms 150052 KB Output is correct
18 Correct 82 ms 150072 KB Output is correct
19 Correct 82 ms 150084 KB Output is correct
20 Correct 80 ms 150076 KB Output is correct
21 Correct 83 ms 150076 KB Output is correct
22 Correct 85 ms 150068 KB Output is correct
23 Correct 80 ms 150008 KB Output is correct
24 Correct 80 ms 149936 KB Output is correct
25 Correct 109 ms 156964 KB Output is correct
26 Correct 107 ms 157028 KB Output is correct
27 Correct 95 ms 157120 KB Output is correct
28 Correct 92 ms 157016 KB Output is correct
29 Correct 95 ms 157344 KB Output is correct
30 Correct 98 ms 157472 KB Output is correct
31 Correct 99 ms 157360 KB Output is correct
32 Correct 94 ms 157372 KB Output is correct
33 Correct 79 ms 147372 KB Output is correct
34 Correct 79 ms 147388 KB Output is correct
35 Correct 78 ms 148140 KB Output is correct
36 Correct 81 ms 148076 KB Output is correct
37 Correct 91 ms 147524 KB Output is correct
38 Correct 292 ms 222020 KB Output is correct
39 Correct 267 ms 221816 KB Output is correct
40 Correct 263 ms 221852 KB Output is correct
41 Correct 264 ms 221888 KB Output is correct
42 Correct 327 ms 223424 KB Output is correct
43 Correct 333 ms 223516 KB Output is correct
44 Correct 344 ms 223704 KB Output is correct
45 Correct 371 ms 222772 KB Output is correct
46 Correct 280 ms 222036 KB Output is correct
47 Correct 290 ms 223228 KB Output is correct
48 Correct 346 ms 227068 KB Output is correct
49 Correct 360 ms 228908 KB Output is correct
50 Correct 278 ms 220180 KB Output is correct
51 Correct 311 ms 218692 KB Output is correct
52 Correct 331 ms 227288 KB Output is correct
53 Correct 355 ms 228264 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1995 ms 755528 KB Output is correct
2 Correct 1422 ms 621632 KB Output is correct
3 Correct 1890 ms 755356 KB Output is correct
4 Correct 80 ms 147396 KB Output is correct
5 Correct 1961 ms 755408 KB Output is correct
6 Correct 1972 ms 755544 KB Output is correct
7 Correct 1967 ms 755396 KB Output is correct
8 Correct 2035 ms 755456 KB Output is correct
9 Correct 1980 ms 755404 KB Output is correct
10 Correct 1900 ms 755104 KB Output is correct
11 Correct 1969 ms 755344 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 147372 KB Output is correct
2 Correct 79 ms 147388 KB Output is correct
3 Correct 78 ms 148140 KB Output is correct
4 Correct 81 ms 148076 KB Output is correct
5 Correct 91 ms 147524 KB Output is correct
6 Correct 89 ms 147564 KB Output is correct
7 Correct 2349 ms 765908 KB Output is correct
8 Correct 3053 ms 876804 KB Output is correct
9 Correct 3072 ms 877592 KB Output is correct
10 Correct 3101 ms 877588 KB Output is correct
11 Correct 2039 ms 791452 KB Output is correct
12 Correct 2013 ms 825656 KB Output is correct
13 Correct 2045 ms 828672 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 147520 KB Output is correct
2 Correct 79 ms 148124 KB Output is correct
3 Correct 84 ms 148200 KB Output is correct
4 Correct 91 ms 148244 KB Output is correct
5 Correct 79 ms 148188 KB Output is correct
6 Correct 80 ms 148084 KB Output is correct
7 Correct 80 ms 148100 KB Output is correct
8 Correct 89 ms 148076 KB Output is correct
9 Correct 80 ms 148088 KB Output is correct
10 Correct 79 ms 148180 KB Output is correct
11 Correct 81 ms 148128 KB Output is correct
12 Correct 87 ms 148164 KB Output is correct
13 Correct 81 ms 147396 KB Output is correct
14 Correct 80 ms 147504 KB Output is correct
15 Correct 82 ms 147596 KB Output is correct
16 Correct 80 ms 147396 KB Output is correct
17 Correct 82 ms 150052 KB Output is correct
18 Correct 82 ms 150072 KB Output is correct
19 Correct 82 ms 150084 KB Output is correct
20 Correct 80 ms 150076 KB Output is correct
21 Correct 83 ms 150076 KB Output is correct
22 Correct 85 ms 150068 KB Output is correct
23 Correct 80 ms 150008 KB Output is correct
24 Correct 80 ms 149936 KB Output is correct
25 Correct 109 ms 156964 KB Output is correct
26 Correct 107 ms 157028 KB Output is correct
27 Correct 95 ms 157120 KB Output is correct
28 Correct 92 ms 157016 KB Output is correct
29 Correct 95 ms 157344 KB Output is correct
30 Correct 98 ms 157472 KB Output is correct
31 Correct 99 ms 157360 KB Output is correct
32 Correct 94 ms 157372 KB Output is correct
33 Correct 292 ms 222020 KB Output is correct
34 Correct 267 ms 221816 KB Output is correct
35 Correct 263 ms 221852 KB Output is correct
36 Correct 264 ms 221888 KB Output is correct
37 Correct 327 ms 223424 KB Output is correct
38 Correct 333 ms 223516 KB Output is correct
39 Correct 344 ms 223704 KB Output is correct
40 Correct 371 ms 222772 KB Output is correct
41 Correct 280 ms 222036 KB Output is correct
42 Correct 290 ms 223228 KB Output is correct
43 Correct 346 ms 227068 KB Output is correct
44 Correct 360 ms 228908 KB Output is correct
45 Correct 278 ms 220180 KB Output is correct
46 Correct 311 ms 218692 KB Output is correct
47 Correct 331 ms 227288 KB Output is correct
48 Correct 355 ms 228264 KB Output is correct
49 Correct 1995 ms 755528 KB Output is correct
50 Correct 1422 ms 621632 KB Output is correct
51 Correct 1890 ms 755356 KB Output is correct
52 Correct 80 ms 147396 KB Output is correct
53 Correct 1961 ms 755408 KB Output is correct
54 Correct 1972 ms 755544 KB Output is correct
55 Correct 1967 ms 755396 KB Output is correct
56 Correct 2035 ms 755456 KB Output is correct
57 Correct 1980 ms 755404 KB Output is correct
58 Correct 1900 ms 755104 KB Output is correct
59 Correct 1969 ms 755344 KB Output is correct
60 Correct 89 ms 147564 KB Output is correct
61 Correct 2349 ms 765908 KB Output is correct
62 Correct 3053 ms 876804 KB Output is correct
63 Correct 3072 ms 877592 KB Output is correct
64 Correct 3101 ms 877588 KB Output is correct
65 Correct 2039 ms 791452 KB Output is correct
66 Correct 2013 ms 825656 KB Output is correct
67 Correct 2045 ms 828672 KB Output is correct
68 Correct 79 ms 147372 KB Output is correct
69 Correct 79 ms 147388 KB Output is correct
70 Correct 78 ms 148140 KB Output is correct
71 Correct 81 ms 148076 KB Output is correct
72 Correct 91 ms 147524 KB Output is correct
73 Correct 2681 ms 860872 KB Output is correct
74 Correct 2731 ms 851632 KB Output is correct
75 Correct 2617 ms 851960 KB Output is correct
76 Correct 2641 ms 851608 KB Output is correct
77 Correct 3807 ms 895644 KB Output is correct
78 Correct 3215 ms 874300 KB Output is correct
79 Correct 3396 ms 897804 KB Output is correct
80 Correct 4062 ms 953836 KB Output is correct
81 Correct 3312 ms 889688 KB Output is correct
82 Correct 3754 ms 920152 KB Output is correct
83 Correct 4110 ms 955200 KB Output is correct
84 Correct 3020 ms 877692 KB Output is correct
85 Correct 3759 ms 947948 KB Output is correct
86 Correct 3765 ms 941924 KB Output is correct
87 Correct 3350 ms 862400 KB Output is correct
88 Correct 4204 ms 889412 KB Output is correct
89 Correct 4182 ms 883092 KB Output is correct
90 Correct 4119 ms 878556 KB Output is correct