제출 #268145

#제출 시각아이디문제언어결과실행 시간메모리
268145dooweyRectangles (IOI19_rect)C++14
0 / 100
1110 ms393216 KiB
#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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...