Submission #667467

#TimeUsernameProblemLanguageResultExecution timeMemory
667467flappybirdRectangles (IOI19_rect)C++17
0 / 100
56 ms46068 KiB
#include "rect.h" #include <bits/stdc++.h> #include <cassert> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define MAX 26 int N, M; vector<short> axis[2][MAX][MAX]; vector<short> endp[2][MAX][MAX]; int ans = 0; long long count_rectangles(std::vector<std::vector<int> > A) { N = A.size(); M = A[0].size(); int i, j; for (i = 0; i < N; i++) { vector<pii> st; for (j = 0; j < M; j++) { int cc = 1; while (st.size() && st.back().first <= A[i][j]) { if (st.back().first == A[i][j]) cc = 0; if (st.back().second + 1 <= j - 1) { axis[1][st.back().second + 1][j - 1].push_back(i); endp[1][i][st.back().second + 1].push_back(j - 1); } st.pop_back(); } if (cc && st.size() && st.back().second + 1 <= j - 1) { axis[1][st.back().second + 1][j - 1].push_back(i); endp[1][i][st.back().second + 1].push_back(j - 1); } st.emplace_back(A[i][j], j); } } for (i = 0; i < M; i++) { vector<pii> st; for (j = 0; j < N; j++) { int cc = 1; while (st.size() && st.back().first <= A[j][i]) { if (st.back().first == A[j][i]) cc = 0; if (st.back().second + 1 <= j - 1) { axis[0][st.back().second + 1][j - 1].push_back(i); endp[0][st.back().second + 1][i].push_back(j - 1); } st.pop_back(); } if (cc && st.size() && st.back().second + 1 <= j - 1) { axis[0][st.back().second + 1][j - 1].push_back(i); endp[0][st.back().second + 1][i].push_back(j - 1); } st.emplace_back(A[j][i], j); } } int allcnt = 0; for (i = 1; i < N - 1; ++i) for (j = 1; j < M - 1; ++j) for (auto ii : endp[0][i][j]) for (auto jj : endp[1][i][j]) { if (i > ii || j > jj || ii >= N - 1 || jj >= M - 1 || i <= 0 || j <= 0) continue; allcnt++; assert(allcnt < 7000000); short ind1, ind2; ind1 = lower_bound(axis[0][i][ii].begin(), axis[0][i][ii].end(), j) - axis[0][i][ii].begin(); ind2 = lower_bound(axis[0][i][ii].begin(), axis[0][i][ii].end(), jj) - axis[0][i][ii].begin(); if (ind1 >= axis[0][i][ii].size()) continue; if (ind2 >= axis[0][i][ii].size()) continue; if (j != axis[0][i][ii][ind1]) continue; if (jj != axis[0][i][ii][ind2]) continue; if (jj - j != ind2 - ind1) continue; ind1 = lower_bound(axis[1][j][jj].begin(), axis[1][j][jj].end(), i) - axis[1][j][jj].begin(); ind2 = lower_bound(axis[1][j][jj].begin(), axis[1][j][jj].end(), ii) - axis[1][j][jj].begin(); if (ind1 >= axis[1][j][jj].size()) continue; if (ind2 >= axis[1][j][jj].size()) continue; if (i != axis[1][j][jj][ind1]) continue; if (ii != axis[1][j][jj][ind2]) continue; if (ii - i != ind2 - ind1) continue; ans++; } return ans; }

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:62:12: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   if (ind1 >= axis[0][i][ii].size()) continue;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:63:12: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if (ind2 >= axis[0][i][ii].size()) continue;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:69:12: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   if (ind1 >= axis[1][j][jj].size()) continue;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:70:12: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   if (ind2 >= axis[1][j][jj].size()) continue;
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...