Submission #266923

#	Time	Username	Problem	Language	Result	Execution time	Memory
266923		alexandra_udristoiu	Rectangles (IOI19_rect)	C++14	72 / 100	5126 ms	1000060 KiB

rect

#include<iostream>
#include<vector>
#include<algorithm>
#include "rect.h"
using namespace std;
static int a[2505][2505], d[4][2505][2505], c[2505], df[4][2505][2505], lst[2505][2505];
static vector<int> lin[2505][2505], col[2505][2505];
static int verif(int i, int j, int ii, int jj){
    if(i == 0 || j == 0 || i == ii - 1 || j == jj - 1){
        return 0;
    }
    if( (d[0][ii - 1][jj] == j && df[0][ii - 1][jj] <= i + 1) || (d[1][ii - 1][j] == jj && df[1][ii - 1][j] <= i + 1) ){
        if( (d[2][ii][jj - 1] == i && df[2][ii][jj - 1] <= j + 1) || (d[3][i][jj - 1] == ii && df[3][i][jj - 1] <= j + 1) ){
            return 1;
        }
        else{
            return -1;
        }
    }
    return 0;
}
int cmp(int a, int b){
    return a > b;
}

long long count_rectangles(std::vector<std::vector<int> > a1) {
	int n, m, i, j, ii, jj, u, x;
	long long sol = 0;
	n = a1.size();
	m = a1[0].size();
	for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            a[i][j] = a1[i - 1][j - 1];
        }
	}

	for(i = 1; i <= n; i++){
        u = 0;
        c[0] = 0;
        for(j = 1; j <= m; j++){
            while(u > 0 && a[i][ c[u] ] < a[i][j]){
                u--;
            }
            d[0][i][j] = c[u];
            col[i + 1][j].push_back(c[u]);
            c[++u] = j;
        }
        u = 0;
        c[0] = m + 1;
        for(j = m; j >= 1; j--){
            while(u > 0 && a[i][ c[u] ] < a[i][j]){
                u--;
            }
            d[1][i][j] = c[u];
            if(a[i][ c[u] ] != a[i][j]){
                col[i + 1][ c[u] ].push_back(j);
            }
            c[++u] = j;
        }
	}
	for(j = 1; j <= m; j++){
        u = 0;
        c[0] = 0;
        for(i = 1; i <= n; i++){
            while(u > 0 && a[ c[u] ][j] < a[i][j]){
                u--;
            }
            d[2][i][j] = c[u];
            lin[i][j + 1].push_back(c[u]);
            c[++u] = i;
        }
        u = 0;
        c[0] = n + 1;
        for(i = n; i >= 1; i--){
            while(u > 0 && a[ c[u] ][j] < a[i][j]){
                u--;
            }
            d[3][i][j] = c[u];
            if(a[ c[u] ][j] != a[i][j]){
                lin[ c[u] ][j + 1].push_back(i);
            }
            c[++u] = i;
        }
	}

    for(i = 1; i <= n; i++){
        for(ii = 0; ii < 2; ii++){
            for(j = 1; j <= m; j++){
                df[ii][i][j] = i;
                if(d[ii][i - 1][j] == d[ii][i][j]){
                    df[ii][i][j] = df[ii][i - 1][j];
                }
                else if(d[1 - ii][i - 1][ d[ii][i][j] ] == j){
                    df[ii][i][j] = df[1 - ii][i - 1][ d[ii][i][j] ];
                }
            }
        }
    }
    for(j = 1; j <= m; j++){
        for(ii = 2; ii < 4; ii++){
            for(i = 1; i <= n; i++){
                df[ii][i][j] = j;
                if(d[ii][i][j - 1] == d[ii][i][j]){
                    df[ii][i][j] = df[ii][i][j - 1];
                }
                else if(d[5 - ii][  d[ii][i][j]  ][j - 1] == i){
                    df[ii][i][j] = df[5 - ii][  d[ii][i][j]  ][j - 1];
                }
            }
        }
    }

    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            sort(col[i][j].begin(), col[i][j].end(), cmp);
            for(ii = 0; ii < lin[i][j].size(); ii++){
                for(jj = 0; jj < col[i][j].size(); jj++){
                    x = verif(lin[i][j][ii], col[i][j][jj], i, j);
                    if(x == -1){
                        break;
                    }
                    sol += x;
                }
            }
        }
    }
    return sol;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:116:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for(ii = 0; ii < lin[i][j].size(); ii++){
      |                         ~~~^~~~~~~~~~~~~~~~~~
rect.cpp:117:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                 for(jj = 0; jj < col[i][j].size(); jj++){
      |                             ~~~^~~~~~~~~~~~~~~~~~
rect.cpp: At global scope:
rect.cpp:6:73: warning: 'lst' defined but not used [-Wunused-variable]
    6 | static int a[2505][2505], d[4][2505][2505], c[2505], df[4][2505][2505], lst[2505][2505];
      |                                                                         ^~~

• 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: 0 / 28