제출 #1106010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106010		snpmrnhlol	Rectangles (IOI19_rect)	C++17	13 / 100	1343 ms	667176 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
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;
vector <int> righ[N][N];
vector <int> down[N][N];
int rightspec[N][N];
int leftspec[N][N];
int downspec[N][N];
int upspec[N][N];
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};
}
pair<int,int> get(int x, int y, int dir){
    if(dir == 0){
        return {x, nxt[0][x][y]};
    }else if(dir == 1){
        pair<int,int> f2 = rot(x, y, 1);
        return {rot(0, nxt[1][f2.first][f2.second], 3, m, n).first, y};
    }else if(dir == 2){
        pair<int,int> f2 = rot(x, y, 2);
        return {x, rot(0, nxt[2][f2.first][f2.second], 2).second};
    }else{
        pair<int,int> f2 = rot(x, y, 3);
        return {rot(0, nxt[3][f2.first][f2.second], 1, m, n).first, 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);
        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;
    }
    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);
        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;
}
bool checkfast(int x, int y, int x2, int y2){
    if(x == 0 || y == 0 || x2 == n - 1 || y2 == m - 1)return 0;
    //cout<<upspec[x2 + 1][y2]<<' '<<get(x2 + 1,y2,1).first<<' '<<x<<'\n';
    if(!((upspec[x2 + 1][y2] <= y && get(x2 + 1,y2,1).first == x - 1) || (downspec[x - 1][y2] <= y && get(x - 1, y2, 3).first == x2 + 1)))return 0;
    if(!((rightspec[x2][y - 1] <= x && get(x2,y - 1,0).second == y2 + 1) || (leftspec[x2][y2 + 1] <= x && get(x2, y2 + 1, 2).second == y - 1)))return 0;
    return 1;
}
long long count_rectangles(std::vector<std::vector<int>> a) {
    auto checkslow = [&](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;
    };
    auto rightadd = [&](int x, int y, int p) -> void{
        if(0 <= x && x < n && 0 <= y && y < m && 0 <= p && p < m && y <= p){
            righ[x][y].push_back(p);
        }
    };
    auto downadd = [&](int x, int y, int p) -> void{
        if(0 <= x && x < n && 0 <= y && y < m && 0 <= p && p < n && x <= p){
            down[x][y].push_back(p);
        }
    };
    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);
    }
    /*
    for(int deg = 0;deg < 4;deg++){
        for(int i = 0;i < n2;i++){
            for(int j = 0;j < m2;j++){
                if(i == 0){
                    v3[deg][i][j] = i;
                }else{
                    pair<int,int> f = rot(i, nxt[deg][i][j], 2, n2, m2);
                    ///maybe f is infinite??
                    if(nxt[deg][i - 1][j] == nxt[deg][i][j] || rot(i, nxt[(deg + 2)%4][f.first][f.second], 2, n2, m2).second == i){
                        v3[deg][i][j] = v3[deg][i - 1][j];
                    }else{
                        v3[deg][i][j] = i;
                    }
                }
            }
        }
        swap(n2,m2);
    }
    */
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            rightspec[i][j] = i;
            leftspec[i][j] = i;
            if(i){
                int r = get(i, j, 0).second;
                if(r == get(i - 1, j, 0).second){
                    rightspec[i][j] = rightspec[i - 1][j];
                }else if(j == get(i - 1, r, 2).second){
                    rightspec[i][j] = leftspec[i - 1][r];
                }
                int l = get(i, j, 2).second;
                if(l == get(i - 1, j, 2).second){
                    leftspec[i][j] = leftspec[i - 1][j];
                }else if(j == get(i - 1, l, 0).second){
                    leftspec[i][j] = rightspec[i - 1][l];
                }
            }
        }
    }
    for(int j = 0;j < m;j++){
        for(int i = 0;i < n;i++){
            upspec[i][j] = j;
            downspec[i][j] = j;
            if(j){
                int u = get(i, j, 1).first;
                if(u == get(i, j - 1, 1).first){
                    upspec[i][j] = upspec[i][j - 1];
                }else if(i == get(u, j - 1, 3).first){
                    upspec[i][j] = downspec[u][j - 1];
                }
                int d = get(i, j, 3).first;
                if(d == get(i, j - 1, 3).first){
                    downspec[i][j] = downspec[i][j - 1];
                }else if(i == get(d, j - 1, 1).first){
                    downspec[i][j] = downspec[d][j - 1];
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            pair<int,int> t = rot(i,j,2);
            if(j)rightadd(i, j, nxt[0][i][j - 1] - 1);
            rightadd(i, get(i, j, 2).second + 1, j - 1);
            if(i)downadd(i, j, get(i - 1, j, 3).first - 1);
            downadd(get(i, j, 1).first + 1, j, i - 1);
        }
    }

    for(int i = 1;i < n - 1;i++){
        for(int j = 1;j < m - 1;j++){
            ///n^2 checks max?
            sort(righ[i][j].begin(),righ[i][j].end());
            righ[i][j].erase(unique(righ[i][j].begin(),righ[i][j].end()),righ[i][j].end());
            sort(down[i][j].begin(),down[i][j].end());
            down[i][j].erase(unique(down[i][j].begin(),down[i][j].end()),down[i][j].end());
            for(auto l:down[i][j]){
                for(auto k:righ[i][j]){
                    assert(j <= k && k <= m - 1);
                    if(checkfast(i,j,l,k)){
                        //cout<<i<<' '<<j<<' '<<l<<' '<<k<<'\n';
                        ans++;
                    }
                }
            }
        }
    }

    //checkfast(1,1,1,1);
	return ans;
}
/**
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
**/

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:100:21: warning: unused variable 'nr' [-Wunused-variable]
  100 |                 int nr = na[i][j];
      |                     ^~
rect.cpp:173:27: warning: variable 't' set but not used [-Wunused-but-set-variable]
  173 |             pair<int,int> t = rot(i,j,2);
      |                           ^
rect.cpp:63:10: warning: variable 'checkslow' set but not used [-Wunused-but-set-variable]
   63 |     auto checkslow = [&](int x, int y, int x2, int y2) -> bool{
      |          ^~~~~~~~~

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