oj.uz

Submission #268145

# Submission time Handle Problem Language Result Execution time Memory
268145 2020-08-16T09:29:43 Z doowey Rectangles (IOI19_rect) C++14
0 / 100
 1110 ms 393216 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 295160 KB Output is correct
2 Correct 185 ms 295560 KB Output is correct
3 Correct 185 ms 295544 KB Output is correct
4 Correct 187 ms 295672 KB Output is correct
5 Correct 195 ms 295528 KB Output is correct
6 Incorrect 202 ms 295544 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 295160 KB Output is correct
2 Correct 185 ms 295560 KB Output is correct
3 Correct 185 ms 295544 KB Output is correct
4 Correct 187 ms 295672 KB Output is correct
5 Correct 195 ms 295528 KB Output is correct
6 Incorrect 202 ms 295544 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 295160 KB Output is correct
2 Correct 185 ms 295560 KB Output is correct
3 Correct 185 ms 295544 KB Output is correct
4 Correct 187 ms 295672 KB Output is correct
5 Correct 195 ms 295528 KB Output is correct
6 Incorrect 202 ms 295544 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 295160 KB Output is correct
2 Correct 185 ms 295560 KB Output is correct
3 Correct 185 ms 295544 KB Output is correct
4 Correct 187 ms 295672 KB Output is correct
5 Correct 195 ms 295528 KB Output is correct
6 Incorrect 202 ms 295544 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 295420 KB Output is correct
2 Correct 217 ms 295416 KB Output is correct
3 Correct 215 ms 295288 KB Output is correct
4 Correct 187 ms 295032 KB Output is correct
5 Incorrect 200 ms 295544 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 295288 KB Output is correct
2 Incorrect 1110 ms 393216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 295160 KB Output is correct
2 Correct 185 ms 295560 KB Output is correct
3 Correct 185 ms 295544 KB Output is correct
4 Correct 187 ms 295672 KB Output is correct
5 Correct 195 ms 295528 KB Output is correct
6 Incorrect 202 ms 295544 KB Output isn't correct
7 Halted 0 ms 0 KB -