Submission #266973

#	Time	Username	Problem	Language	Result	Execution time	Memory
266973		alexandra_udristoiu	Rectangles (IOI19_rect)	C++14	100 / 100	3496 ms	542764 KiB

rect

#include<iostream>
#include<set>
#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 int n, m, nr;
struct str{
    int a, b, c, d;
};
vector<str> w;
int cmp(str x, str y){
    if(x.a != y.a){
        return x.a < y.a;
    }
    if(x.b != y.b){
        return x.b < y.b;
    }
    if(x.c != y.c){
        return x.c < y.c;
    }
    return x.d < y.d;
}
static void verif(int i, int j, int ii, int jj){
    if(i > ii){
        swap(i, ii);
    }
    if(j > jj){
        swap(j, jj);
    }
    if(i == 0 || j == 0 || i >= ii - 1 || j >= jj - 1 || ii == n + 1 || jj == m + 1){
        return;
    }
    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) ){
            w.push_back( {i, j, ii, jj} );
        }
    }
}

long long count_rectangles(std::vector<std::vector<int> > a1) {
	int 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];
            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];
            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];
            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];
            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 = 2; i < n; i++){
        for(j = 2; j < m; j++){
            verif(i + 1, j + 1, d[2][i + 1][j], d[0][i][j + 1]);
            verif(i + 1, j - 1, d[2][i + 1][j], d[1][i][j - 1]);
            x = d[3][i - 1][j];
            verif(i - 1, j - 1, x, d[1][i][j - 1]);
            verif(i - 1, j + 1, x, d[0][i][j + 1]);
            verif(i - 1, j - 1, x, d[1][x - 1][j - 1]);
            verif(i - 1, j + 1, x, d[0][x - 1][j + 1]);
        }
    }
    sort(w.begin(), w.end(), cmp);
    if(w.size() == 0){
        return 0;
    }
    sol = 1;
    for(i = 1; i < w.size(); i++){
        if(w[i].a != w[sol - 1].a || w[i].b != w[sol - 1].b || w[i].c != w[sol - 1].c || w[i].d != w[sol - 1].d ){
            w[++sol - 1] = w[i];
        }
    }
    return sol;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:137:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(i = 1; i < w.size(); i++){
      |                ~~^~~~~~~~~~
rect.cpp:43:16: warning: unused variable 'jj' [-Wunused-variable]
   43 |  int i, j, ii, jj, u, x;
      |                ^~
rect.cpp: At global scope:
rect.cpp:8:18: warning: 'nr' defined but not used [-Wunused-variable]
    8 | static int n, m, nr;
      |                  ^~
rect.cpp:7:73: warning: 'lst' defined but not used [-Wunused-variable]
    7 | 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: 28 / 28