Submission #1105951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105951		snpmrnhlol	Rectangles (IOI19_rect)	C++17	37 / 100	5093 ms	114744 KiB

rect

#include "rect.h"
#include <iostream>
using namespace std;
const int N = 25e2;
const int inf = N + 1;
int nxt[4][N][N];
int prv[N][N];
int na[N][N];
int v2[N], cnt = 0;
int n, m;
pair<int,int> rot(int x, int y, int deg, int n2 = n,int m2 = m){
    for(int i = 0;i < deg;i++){
        swap(x,y);
        y = n2 - 1 - y;
        swap(n2,m2);
    }
    return {x,y};
}
bool check(int x, int y, int x2, int y2){
    if(x == 0 || y == 0 || x2 == n - 1 || y2 == m - 1)return 0;
    for(int i = y;i <= y2;i++){
        pair<int,int> f = rot(x - 1, i, 3);
        pair<int,int> f2 = rot(x2 + 1, i, 1);
        //cout<<f.first<<' '<<f.second<<' '<<f2.first<<' '<<f2.second<<' '<<nxt[3][f.first][f.second]<<' '<<nxt[1][f2.first][f2.second]<<' '<<rot(0, nxt[3][f.first][f.second], 1, m, n).first<<' '<<rot(0, nxt[1][f2.first][f2.second], 3, m, n).first<<'\n';
        if(rot(0, nxt[3][f.first][f.second], 1, m, n).first <= x2)return 0;
        if(rot(0, nxt[1][f2.first][f2.second], 3, m, n).first >= x)return 0;
    }
    //cout<<"??\n";
    for(int i = x;i <= x2;i++){
        pair<int,int> f = rot(i, y - 1, 0);
        pair<int,int> f2 = rot(i, y2 + 1, 2);
        //cout<<f2.first<<' '<<f2.second<<' '<<nxt[2][f2.first][f2.second]<<' '<<rot(0, nxt[2][f2.first][f2.second], 2).second<<'\n';
        if(nxt[0][f.first][f.second] <= y2)return 0;
        if(rot(0, nxt[2][f2.first][f2.second], 2).second >= y)return 0;
    }
    return 1;
}
long long count_rectangles(std::vector<std::vector<int>> a) {
    auto check2 = [&](int x, int y, int x2, int y2) -> bool{
        if(x == 0 || y == 0 || x2 == n - 1 || y2 == m - 1)return 0;
        for(int i = x;i <= x2;i++){
            for(int j = y;j <= y2;j++){
                if(a[i][j] >= a[x - 1][j])return 0;
                if(a[i][j] >= a[x2 + 1][j])return 0;
                if(a[i][j] >= a[i][y - 1])return 0;
                if(a[i][j] >= a[i][y2 + 1])return 0;
            }
        }
        return 1;
    };
    n = a.size();
    m = a[0].size();
    int n2 = n;
    int m2 = m;
    for(int deg = 0;deg < 4;deg++){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                pair <int,int> f = rot(i, j, deg);
                na[f.first][f.second] = a[i][j];
                nxt[deg][f.first][f.second] = inf;
            }
        }
        for(int i = 0;i < n2;i++){
            cnt = 0;
            for(int j = 0;j < m2;j++){
                int nr = na[i][j];
                while(cnt > 0 && na[i][v2[cnt - 1]] <= na[i][j]){
                    nxt[deg][i][v2[cnt - 1]] = j;
                    cnt--;
                }
                v2[cnt++] = j;
            }
        }
        swap(n2,m2);
    }
    int ans = 0;

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            for(int k = i;k < n;k++){
                for(int p = j;p < m;p++){
                    if(check(i,j,k,p)){
                        ans++;
                        //cout<<i<<' '<<j<<' '<<k<<' '<<p<<'\n';
                    }
                }
            }
        }
    }
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:66:21: warning: unused variable 'nr' [-Wunused-variable]
   66 |                 int nr = na[i][j];
      |                     ^~
rect.cpp:39:10: warning: variable 'check2' set but not used [-Wunused-but-set-variable]
   39 |     auto check2 = [&](int x, int y, int x2, int y2) -> bool{
      |          ^~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28