Submission #164294

#TimeUsernameProblemLanguageResultExecution timeMemory
164294AnaiRectangles (IOI19_rect)C++14
0 / 100
155 ms148248 KiB
#include "rect.h" #include <bits/stdc++.h> #define x first #define y second using namespace std; using i64 = long long; using pii = pair<int, int>; const int S = 2500 * 2500 + 5, N = 2505; const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; vector<pii> qs[N][N]; bool bad[N][N]; vector<pair<pii, pii>> trims; vector<vector<int>> mx; vector<vector<int>> lf, rt, bt, tp; int n, m; static void scanner() { lf = vector<vector<int>>(n, vector<int>(m)); rt = vector<vector<int>>(n, vector<int>(m)); tp = vector<vector<int>>(n, vector<int>(m)); bt = vector<vector<int>>(n, vector<int>(m)); for (int i = 0; i < n; ++i) { vector<int> stk; for (int j = 0; j < m; ++j) { // left while (!stk.empty() && mx[i][stk.back()] <= mx[i][j]) stk.pop_back(); lf[i][j] = stk.empty() ? -1 : stk.back(); stk.push_back(j); } stk.clear(); for (int j = m - 1; j > 0; --j) { // right while (!stk.empty() && mx[i][stk.back()] <= mx[i][j]) stk.pop_back(); rt[i][j] = stk.empty() ? -1 : stk.back(); stk.push_back(j); } } for (int j = 0; j < m; ++j) { vector<int> stk; for (int i = 0; i < n - 1; ++i) { // top while (!stk.empty() && mx[stk.back()][j] <= mx[i][j]) stk.pop_back(); tp[i][j] = stk.empty() ? -1 : stk.back(); stk.push_back(i); } stk.clear(); for (int i = n - 1; i > 0; --i) { // bottom while (!stk.empty() && mx[stk.back()][j] <= mx[i][j]) stk.pop_back(); bt[i][j] = stk.empty() ? -1 : stk.back(); stk.push_back(i); } } } static void run_vertical() { vector<int> h_stk, stk[N]; int h[N]; for (int i = 1; i < n - 1; ++i) for (int j = 1; j < m - 1; ++j) { if (rt[i][j] == -1 || lf[i][j] == -1 || tp[i][j] == -1 || bt[i][j] == -1 || bad[i][j]) { bad[i][j] = true; } else { qs[tp[i][j]][rt[i][j] - 1].emplace_back(i, j); qs[bt[i][j]][rt[i][j] - 1].emplace_back(-i, -j); } } // bottom radiates up for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { while (!stk[j].empty() && mx[stk[j].back()][j] < mx[i][j]) stk[j].pop_back(); h[j] = stk[j].empty() ? 0 : stk[j].back(); stk[j].push_back(i); } h_stk.clear(); for (int j = 0; j < m; ++j) { while (!h_stk.empty() && h[h_stk.back()] > h[j]) h_stk.pop_back(); h_stk.push_back(j); for (auto q: qs[i][j]) if (q.x < 0) { // actually query handling int pos = -1, bnd = lf[-q.x][-q.y]; for (int msk = 1 << 11; msk > 0; msk/= 2) if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd) pos+= msk; pos+= 1; if (h[h_stk[pos]] > tp[-q.x][-q.y] && !bad[-q.x][-q.y]) bad[-q.x][-q.y] = true; } } } for (int i = 0; i < N; ++i) stk[i].clear(); // top radiates down for (int i = n - 1; i >= 0; --i) { for (int j = 0; j < m; ++j) { while (!stk[j].empty() && mx[stk[j].back()][j] < mx[i][j]) stk[j].pop_back(); h[j] = stk[j].empty() ? 1e9 : stk[j].back(); stk[j].push_back(i); } h_stk.clear(); for (int j = 0; j < m; ++j) { while (!h_stk.empty() && h[h_stk.back()] < h[j]) h_stk.pop_back(); h_stk.push_back(j); for (auto q: qs[i][j]) if (q.x > 0) { // actually query handling int pos = -1, bnd = lf[q.x][q.y]; for (int msk = 1 << 11; msk > 0; msk/= 2) if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd) pos+= msk; pos+= 1; if (h[h_stk[pos]] < bt[q.x][q.y] && !bad[q.x][q.y]) bad[q.x][q.y] = true; } } } } static void run_horizontal() { vector<int> h_stk, stk[N]; int h[N]; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) qs[i][j].clear(); for (int i = 1; i < n - 1; ++i) for (int j = 1; j < m - 1; ++j) { if (rt[i][j] == -1 || lf[i][j] == -1 || tp[i][j] == -1 || bt[i][j] == -1 || bad[i][j]) { bad[i][j] = true; } else { qs[tp[i][j] + 1][lf[i][j]].emplace_back(i, j); qs[tp[i][j] + 1][rt[i][j]].emplace_back(-i, -j); } } // right radiates left for (int j = 0; j < m; ++j) { for (int i = 0; i < n; ++i) { while (!stk[i].empty() && mx[i][stk[i].back()] < mx[i][j]) stk[i].pop_back(); h[i] = stk[i].empty() ? 0 : stk[i].back(); stk[i].push_back(j); } h_stk.clear(); for (int i = 0; i < n; ++i) { while (!h_stk.empty() && h[h_stk.back()] > h[i]) h_stk.pop_back(); h_stk.push_back(i); for (auto q: qs[i][j]) if (q.x < 0) { // actually query handling int pos = -1, bnd = lf[-q.x][-q.y]; for (int msk = 1 << 11; msk > 0; msk/= 2) if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd) pos+= msk; pos+= 1; if (h[h_stk[pos]] > lf[-q.x][-q.y] && !bad[-q.x][-q.y]) bad[-q.x][-q.y] = true; } } } for (int i = 0; i < N; ++i) stk[i].clear(); // left radiates right for (int j = m - 1; j >= 0; --j) { for (int i = 0; i < n; ++i) { while (!stk[i].empty() && mx[i][stk[i].back()] < mx[i][j]) stk[i].pop_back(); h[i] = stk[i].empty() ? 1e9 : stk[i].back(); stk[i].push_back(j); } h_stk.clear(); for (int i = 0; i < n; ++i) { while (!h_stk.empty() && h[h_stk.back()] < h[i]) h_stk.pop_back(); h_stk.push_back(i); for (auto q: qs[i][j]) if (q.x > 0) { // actually query handling int pos = -1, bnd = rt[q.x][q.y]; for (int msk = 1 << 11; msk > 0; msk/= 2) if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd) pos+= msk; pos+= 1; if (h[h_stk[pos]] < rt[q.x][q.y] && !bad[q.x][q.y]) bad[q.x][q.y] = true; } } } } static void pulatronizate() { for (int i = 1; i + 1 < n; ++i) for (int j = 1; j + 1 < m; ++j) if (!bad[i][j]) { trims.emplace_back(pii(lf[i][j], tp[i][j]), pii(rt[i][j], bt[i][j])); } } i64 count_rectangles(vector<vector<int>> _mx) { n = _mx.size(), m = _mx[0].size(); swap(mx, _mx); scanner(); run_vertical(); run_horizontal(); pulatronizate(); sort(begin(trims), end(trims)); trims.erase(unique(begin(trims), end(trims)), end(trims)); return trims.size(); }

Compilation message (stderr)

rect.cpp: In function 'void run_vertical()':
rect.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:118:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp: In function 'void run_horizontal()':
rect.cpp:157:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:183:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
#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...