Submission #268145

#	Time	Username	Problem	Language	Result	Execution time	Memory
268145		doowey	Rectangles (IOI19_rect)	C++14	0 / 100	1110 ms	393216 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;

typedef long long ll;
typedef pair<short, short> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 2505;
vector<int> I[N][N], J[N][N];

int L[N][N], R[N][N], U[N][N], D[N][N];

bool check(int i1, int j1, int i2, int j2){
    if(i1 == -1 || j1 == -1 || i2 == -1 || j2 == -1) return false;
    int il = lower_bound(I[j1][j2].begin(), I[j1][j2].end(), i1+1) - I[j1][j2].begin();
    int ir = upper_bound(I[j1][j2].begin(), I[j1][j2].end(), i2-1) - I[j1][j2].begin();
    ir -- ;
    if(ir - il + 1 != (i2-1)-(i1+1)+1) return false;
    il = lower_bound(J[i1][i2].begin(), J[i1][i2].end(), j1+1) - J[i1][i2].begin();
    ir = lower_bound(J[i1][i2].begin(), J[i1][i2].end(), j2-1) - J[i1][i2].begin();
    if(ir - il + 1 != (j2-1)-(j1+1)+1) return false;
    return true;
}

ll count_rectangles(vector<vector<int>> a){
    int n = a.size();
    int m = a[0].size();
    for(int i = 0 ; i < n; i ++ ){
        vector<int> st;
        for(int j = 0 ; j < m ; j ++ ){
            L[i][j] = -1;
            while(!st.empty() && a[i][st.back()] <= a[i][j]) st.pop_back();
            if(!st.empty()) L[i][j] = st.back();
            st.push_back(j);
        }
        st.clear();
        for(int j = 0 ; j < m ; j ++ ){
            while(!st.empty() && a[i][st.back()] < a[i][j]) st.pop_back();
            if(!st.empty()){
                if(st.back() + 1 < j)I[st.back()][j].push_back(i);
            }
            st.push_back(j);
        }
        st.clear();
        for(int j = m-1 ; j >= 0 ; j -- ){
            R[i][j] = -1;
            while(!st.empty() && a[i][st.back()] <= a[i][j]) st.pop_back();
            if(!st.empty()) R[i][j] = st.back();
            st.push_back(j);
        }
        st.clear();
        for(int j = m - 1; j >= 0 ; j -- ){
            while(!st.empty() && a[i][st.back()] < a[i][j]) st.pop_back();
            if(!st.empty()){
                if(j + 1 < st.back())I[j][st.back()].push_back(i);
            }
            st.push_back(j);
        }
    }
    for(int j = 0 ; j < m ; j ++ ){
        vector<int> st;
        for(int i = 0 ; i < n; i ++ ){
            U[i][j] = -1;
            while(!st.empty() && a[st.back()][j] <= a[i][j]) st.pop_back();
            if(!st.empty()) U[i][j] = st.back();
            st.push_back(i);
        }
        st.clear();
        for(int i = 0 ; i < n; i ++ ){
            while(!st.empty() && a[st.back()][j] < a[i][j]) st.pop_back();
            if(!st.empty()){
                if(st.back() + 1 < i)
                    J[st.back()][i].push_back(j);
            }
            st.push_back(i);
        }
        st.clear();
        for(int i = n - 1; i >= 0 ; i -- ){
            D[i][j] = -1;
            while(!st.empty() && a[st.back()][j] <= a[i][j]) st.pop_back();
            if(!st.empty()) D[i][j] = st.back();
            st.push_back(i);
        }
        st.clear();
        for(int i = n - 1; i >= 0; i -- ){
            while(!st.empty() && a[st.back()][j] < a[i][j]) st.pop_back();
            if(!st.empty())
                if(i + 1 < st.back())
                    J[i][st.back()].push_back(j);
            st.push_back(i);
        }
    }
    for(int i = 0; i < m; i ++ ){
        for(int j = i + 1; j < m ; j ++ ){
            sort(I[i][j].begin(), I[i][j].end());
            I[i][j].resize(unique(I[i][j].begin(), I[i][j].end()) - I[i][j].begin());
        }
    }
    for(int i = 0 ; i < n ; i ++ ){
        for(int j = i + 1; j < n ; j ++ ){
            sort(J[i][j].begin(), J[i][j].end());
            J[i][j].resize(unique(J[i][j].begin(), J[i][j].end()) - J[i][j].begin());
        }
    }
    vector<pair<pii, pii>> sols;
    for(int i = 1 ; i + 1 < n; i ++ ){
        for(int j = 1; j + 1 < m ; j ++ ){
            if(check(U[i][j], L[i][j], D[i][j], R[i][j])){
                sols.push_back({mp(U[i][j], L[i][j]), mp(D[i][j], R[i][j])});
            }
        }
    }
    sort(sols.begin(), sols.end());
    sols.resize(unique(sols.begin(), sols.end()) - sols.begin());
    return sols.size();
}

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