제출 #290729

#제출 시각아이디문제언어결과실행 시간메모리
290729IgorIRectangles (IOI19_rect)C++17
72 / 100
5154 ms1044032 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 88888888; const int N = 2512; typedef vector<vector<int> > vvi; typedef vector<int> vi; #define all(x) (x).begin(), (x).end() int le[N][N], ri[N][N], up[N][N], down[N][N]; vector<pair<int, int> > rooted[N][N]; struct query{ int l, r; int x, tm; }; long long count_rectangles(vector<vector<int> > a) { int n = a.size(), m = a[0].size(); for (int i = 0; i < n; i++) { vector<pair<int, int> > st; st.push_back({-1, INF}); for (int j = 0; j < m; j++) { while (st.back().second < a[i][j]) st.pop_back(); le[i][j] = st.back().first; st.push_back({j, a[i][j]}); } } for (int i = 0; i < n; i++) { vector<pair<int, int> > st; st.push_back({m, INF}); for (int j = m - 1; j >= 0; j--) { while (st.back().second < a[i][j]) st.pop_back(); ri[i][j] = st.back().first; st.push_back({j, a[i][j]}); } } for (int j = 0; j < m; j++) { vector<pair<int, int> > st; st.push_back({-1, INF}); for (int i = 0; i < n; i++) { while (st.back().second < a[i][j]) st.pop_back(); up[i][j] = st.back().first; st.push_back({i, a[i][j]}); } } for (int j = 0; j < m; j++) { vector<pair<int, int> > st; st.push_back({n, INF}); for (int i = n - 1; i >= 0; i--) { while (st.back().second < a[i][j]) st.pop_back(); down[i][j] = st.back().first; st.push_back({i, a[i][j]}); } } for (int i = 1; i + 1 < n; i++) { for (int j = 1; j + 1 < m; j++) { { int r = ri[i][j - 1] - 1; int u0 = up[i + 1][j] + 1; int u1 = up[i + 1][r] + 1; int d0 = down[i - 1][j] - 1; int d1 = down[i - 1][r] - 1; rooted[u0][j].push_back({i, r}); rooted[u1][j].push_back({i, r}); rooted[i][j].push_back({d0, r}); rooted[i][j].push_back({d1, r}); } { int l = le[i][j + 1] + 1; int u0 = up[i + 1][l] + 1; int u1 = up[i + 1][j] + 1; int d0 = down[i - 1][l] - 1; int d1 = down[i - 1][j] - 1; rooted[u0][l].push_back({i, j}); rooted[u1][l].push_back({i, j}); rooted[i][l].push_back({d0, j}); rooted[i][l].push_back({d1, j}); } } } int ans = 0; vector<int> res; vector<vector<query> > qd(n); vector<vector<query> > qu(n); vector<vector<query> > qr(m); vector<vector<query> > ql(m); for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { sort(all(rooted[i][j])); rooted[i][j].resize(unique(all(rooted[i][j])) - rooted[i][j].begin()); for (auto p : rooted[i][j]) { int i2 = p.first, j2 = p.second; if (i <= i2 && j <= j2 && i2 < n - 1 && j2 < m - 1) { int t = 1; for (int y = j; y <= j2; y++) if (down[i - 1][y] <= i2) t = 0; for (int y = j; y <= j2; y++) if (up[i2 + 1][y] >= i) t = 0; for (int x = i; x <= i2; x++) if (ri[x][j - 1] <= j2) t = 0; for (int x = i; x <= i2; x++) if (le[x][j2 + 1] >= j) t = 0; ans += t; qd[i - 1].push_back({j, j2, i2 + 1, res.size()}); qu[i2 + 1].push_back({j, j2, i - 1, res.size()}); qr[j - 1].push_back({i, i2, j2 + 1, res.size()}); ql[j2 + 1].push_back({i, i2, j - 1, res.size()}); res.push_back(1); } } rooted[i][j].clear(); } } return ans; }

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

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:123:65: warning: narrowing conversion of 'res.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  123 |                     qd[i - 1].push_back({j, j2, i2 + 1, res.size()});
      |                                                         ~~~~~~~~^~
rect.cpp:124:65: warning: narrowing conversion of 'res.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  124 |                     qu[i2 + 1].push_back({j, j2, i - 1, res.size()});
      |                                                         ~~~~~~~~^~
rect.cpp:125:65: warning: narrowing conversion of 'res.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  125 |                     qr[j - 1].push_back({i, i2, j2 + 1, res.size()});
      |                                                         ~~~~~~~~^~
rect.cpp:126:65: warning: narrowing conversion of 'res.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  126 |                     ql[j2 + 1].push_back({i, i2, j - 1, res.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...