제출 #229705

#제출 시각아이디문제언어결과실행 시간메모리
229705combi1k1Rectangles (IOI19_rect)C++14
컴파일 에러
0 ms0 KiB
#include "rectangles.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ld double #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pb emplace_back #define X first #define Y second const int N = 2e5 + 5; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<vi> mtx; typedef pair<ii,ii> rec; ll count_rectangles(mtx A) { int n = sz(A); int m = sz(A[0]); mtx l(n,vi(m,m + 5)); mtx u(n,vi(m,n + 5)); mtx r(n,vi(m,-5)); mtx d(n,vi(m,-5)); for(int i = 0 ; i < n ; ++i) { stack<int> lef; stack<int> rig; for(int j = 0 ; j < m ; ++j) { while (lef.size() && A[i][lef.top()] < A[i][j]) lef.pop(); if (lef.size()) l[i][j] = lef.top(); lef.push(j); } for(int j = m - 1 ; j >= 0 ; --j) { while (rig.size() && A[i][rig.top()] < A[i][j]) rig.pop(); if (rig.size()) r[i][j] = rig.top(); rig.push(j); } } for(int j = 0 ; j < m ; ++j) { stack<int> lef; stack<int> rig; for(int i = 0 ; i < n ; ++i) { while (lef.size() && A[lef.top()][j] < A[i][j]) lef.pop(); if (lef.size()) u[i][j] = lef.top(); lef.push(i); } for(int i = n - 1 ; i >= 0 ; --i) { while (rig.size() && A[rig.top()][j] < A[i][j]) rig.pop(); if (rig.size()) d[i][j] = rig.top(); rig.push(i); } } mtx f[4]; f[0].assign(n,vi(m,-1)); f[1].assign(n,vi(m,-1)); f[2].assign(n,vi(m,-1)); f[3].assign(n,vi(m,-1)); for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < m ; ++j) { if (i == 0) f[0][i][j] = (l[i][j] < 0), f[1][j][j] = (r[i][j] < 0); else { if (l[i][j] < 0) f[0][i][j] = i + 1; else { if (l[i - 1][j] == l[i][j]) f[0][i][j] = f[0][i - 1][j]; else if (r[i - 1][l[i][j]] == j) f[0][i][j] = f[1][i - 1][l[i][j]]; else f[0][i][j] = i; } if (r[i][j] < 0) f[1][i][j] = i + 1; else { if (r[i - 1][j] == r[i][j]) f[1][i][j] = f[1][i - 1][j]; else if (l[i - 1][r[i][j]] == j) f[1][i][j] = f[0][i - 1][r[i][j]]; else f[1][i][j] = i; } } } for(int j = 0 ; j < m ; ++j) for(int i = 0 ; i < n ; ++i) { if (j == 0) f[2][i][0] = (u[i][j] < 0), f[3][i][0] = (d[i][j] < 0); else { if (u[i][j] < 0) f[2][i][j] = i + 1; else { if (u[i][j - 1] == u[i][j]) f[2][i][j] = f[2][i][j - 1]; else if (d[u[i][j]][j - 1] == i) f[2][i][j] = f[3][u[i][j]][j - 1]; else f[2][i][j] = j; } if (r[i][j] < 0) f[1][i][j] = i + 1; else { if (d[i][j - 1] == d[i][j]) f[3][i][j] = f[3][i][j - 1]; else if (u[d[i][j]][j - 1] == i) f[3][i][j] = f[2][d[i][j]][j - 1]; else f[3][i][j] = j; } } } set<rec> ans; auto check = [&](int L,int R,int U,int D) { if (L > R || U > D) return; if (L < 1 || R > n - 2) return; if (U < 1 || D > n - 2) return; if (u[R + 1][D] != L - 1 && d[L - 1][D] != R + 1) return; if (l[R][D + 1] != U - 1 && r[R][U - 1] != D + 1) return; if (A[R][U - 1] >= A[R][D + 1] && f[0][R][D + 1] > L) return; if (A[R][U - 1] <= A[R][D + 1] && f[1][R][U - 1] > L) return; if (A[L - 1][D] >= A[R + 1][D] && f[2][R + 1][D] > U) return; if (A[L - 1][D] <= A[R + 1][D] && f[3][L - 1][D] > U) return; ans.insert(rec(ii(L,R),ii(U,D))); }; for(int i = 1 ; i < n - 1 ; ++i) for(int j = 1 ; j < m - 1 ; ++j) { check(u[i + 1][j] + 1,i,l[i][j + 1] + 1,j); check(u[i + 1][j] + 1,i,j,r[i][j - 1] - 1); check(i,d[i - 1][j] - 1,l[i][j + 1] + 1,j); check(i,d[i - 1][j] - 1,j,r[i][j - 1] - 1); } return ans.size(); } /*int main() { cerr << count_rectangles({ {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:1:10: fatal error: rectangles.h: No such file or directory
 #include "rectangles.h"
          ^~~~~~~~~~~~~~
compilation terminated.