제출 #264546

#제출 시각아이디문제언어결과실행 시간메모리
264546hamerinRectangles (IOI19_rect)C++17
0 / 100
5052 ms147832 KiB
#include "rect.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; using i64 = long long; using d64 = long double; using pi = pair<int, int>; using pli = pair<i64, i64>; using ti = tuple<int, int, int>; using tli = tuple<i64, i64, i64>; #define iterall(cont) cont.begin(), cont.end() #define prec(n) setprecision(n) << fixed vector<pi> findLegalTuple(const vector<int> &v) { vector<pi> ret; vector<size_t> seq; // monotonic size_t sn = 0; for (size_t i = 0; i < v.size(); i++) { while (sn >= 1 && v[seq.back()] == v[i]) seq.pop_back(), --sn; seq.emplace_back(i), ++sn; // rearrangement while (sn >= 2 && v[seq[sn - 2]] < v[seq[sn - 1]]) { auto tmp = seq[sn - 1]; seq.pop_back(), --sn; seq[sn - 1] = tmp; if (sn >= 2) ret.emplace_back(seq[sn - 2], seq[sn - 1]); } } return ret; } vector<pi> getMaxPos(const vector<int> &v) { size_t N = v.size(); vector<pi> ret(N, {-1, -1}); for (int i = N - 1; i >= 0; i--) { for (int j = i + 1; j < N; j++) { if (ret[j].first == -1 && v[i] > v[j]) ret[j].first = i; } } for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { if (ret[j].second == -1 && v[i] > v[j]) ret[j].second = i; } } return ret; } vector<pi> processToIntervals(const vector<pi> &v) { vector<pi> ret; for (auto [el, _] : v) { if (!ret.empty() && ret.back().second == el - 1) ret.back().second++; else ret.emplace_back(el, el); } return ret; } bool intervalBinarySearch(const vector<pi> &v, pi t) { const size_t N = v.size(); size_t res = -1; size_t s = 0, e = N - 1; while (e - s >= 2) { size_t m = (s + e) >> 1; if (v[m].first <= t.first && t.second <= v[m].second) { res = m; break; } if (v[m].second < t.first) e = m - 1; if (v[m].first > t.second) s = m + 1; } if (v[s].first <= t.first && t.second <= v[s].second) res = s; if (v[e].first <= t.first && t.second <= v[e].second) res = e; return res != -1; } i64 count_rectangles(vector<vector<int>> a) { const size_t N = a.size(); const size_t M = a[0].size(); // transpose vector<vector<int>> b(M, vector<int>(N)); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) b[j][i] = a[i][j]; // get Max Position vector<vector<pi>> aM(N, vector<pi>(M)); vector<vector<pi>> bM(M, vector<pi>(N)); for (int i = 0; i < N; i++) aM[i] = getMaxPos(a[i]); for (int i = 0; i < M; i++) bM[i] = getMaxPos(b[i]); // find Legal Tuple && assign vector<vector<vector<pi>>> aL(M, decltype(aL)::value_type(M)); vector<vector<vector<pi>>> bL(N, decltype(bL)::value_type(N)); for (int i = 0; i < N; i++) { auto Lg = findLegalTuple(a[i]); for (auto [l, r] : Lg) aL[l][r].emplace_back(i, 0); } for (int i = 0; i < M; i++) { auto Lg = findLegalTuple(b[i]); for (auto [l, r] : Lg) bL[l][r].emplace_back(i, 0); } for (auto &vec : aL) for (auto &el : vec) el = processToIntervals(el); for (auto &vec : bL) for (auto &el : vec) el = processToIntervals(el); // Main Logic int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { auto [L, R] = aM[i][j]; auto [T, B] = bM[j][i]; if (L == -1 || R == -1 || T == -1 || B == -1) continue; if (intervalBinarySearch(aL[L][R], {T + 1, B - 1}) && intervalBinarySearch(bL[T][B], {L + 1, R - 1})) ++ans; } } return ans; }

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

rect.cpp: In function 'std::vector<std::pair<int, int> > getMaxPos(const std::vector<int>&)':
rect.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int j = i + 1; j < N; j++) {
      |                             ~~^~~
rect.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < N; i++) {
      |                     ~~^~~
rect.cpp: In function 'bool intervalBinarySearch(const std::vector<std::pair<int, int> >&, pi)':
rect.cpp:94:16: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     return res != -1;
      |            ~~~~^~~~~
rect.cpp: In function 'i64 count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  103 |     for (int i = 0; i < N; i++)
      |                     ~~^~~
rect.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  104 |         for (int j = 0; j < M; j++) b[j][i] = a[i][j];
      |                         ~~^~~
rect.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < N; i++) aM[i] = getMaxPos(a[i]);
      |                     ~~^~~
rect.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i < M; i++) bM[i] = getMaxPos(b[i]);
      |                     ~~^~~
rect.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  117 |     for (int i = 0; i < N; i++) {
      |                     ~~^~~
rect.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < M; i++) {
      |                     ~~^~~
rect.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < N; i++) {
      |                     ~~^~~
rect.cpp:134:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  134 |         for (int j = 0; j < M; j++) {
      |                         ~~^~~
#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...