Submission #420712

#TimeUsernameProblemLanguageResultExecution timeMemory
420712QCFiumRectangles (IOI19_rect)C++14
0 / 100
1 ms460 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") #include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } struct BIT { int n; std::vector<int> data; int all_sum = 0; BIT (int n) : n(n), data(n + 1) {} void add(int i, int val) { for (i++; i <= n; i += i & -i) data[i] += val; all_sum += val; } int sum_left(int r) { int res = 0; for (; r; r -= r & -r) res += data[r]; return res; } int sum_right(int l) { return all_sum - sum_left(l); } }; struct SegTree { int n; std::vector<int> data; SegTree (int n_) { for (n = 1; n < n_; n <<= 1); data.resize(n << 1); } void add(int i, int val) { for (i += n; i; i >>= 1) data[i] += val; } int sum(int l, int r) { int res = 0; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (r & 1) res += data[--r]; if (l & 1) res += data[l++]; } return res; } }; long long count_rectangles(std::vector<std::vector<int> > a) { int n = a.size(); int m = a[0].size(); int64_t res = 0; if (n == 3) { auto solve_sub = [&] (std::vector<int> a) { int n = a.size(); std::deque<int> all; for (int i = n - 1; i >= 0; i--) { if (i <= n - 3) { int tmp = std::lower_bound(all.begin(), all.end(), a[i]) - all.begin(); res += std::max(0, tmp); } while (all.size() && all.front() <= a[i]) all.pop_front(); all.push_front(a[i]); } }; std::vector<int> all{a[1][0]}; for (int i = 1; i < n; i++) { bool ok = i != n - 1 && a[1][i] < a[0][i] && a[1][i] < a[2][i]; if (!ok) { if (all.size() > 1) { all.push_back(a[1][i]); solve_sub(all); } all = {a[1][i]}; } else all.push_back(a[1][i]); } } else if (n <= 700 && m <= 700) { assert(0); assert(n <= 700 && m <= 700); std::vector<std::vector<std::vector<int> > > r1(n, std::vector<std::vector<int> > (m)); for (int i = 1; i + 1 < m; i++) { std::vector<int> cur(m - i, 0); for (int k = n - 2; k >= 1; k--) { int max = -1; for (int j = i + 1; j < m; j++) { max = std::max(max, a[k][j - 1]); if (max < a[k][j] && max < a[k][i - 1]) cur[j - i]++; else cur[j - i] = 0; } r1[k][i] = cur; } } auto calc = [&] (const std::vector<int> &r0, const std::vector<int> &r1) { std::vector<int> all[r0.size()]; for (int k = 1; k < (int) r1.size(); k++) if (r1[k]) all[r1[k]].push_back(k); BIT tree(r1.size()); for (int k = 1; k < (int) r0.size(); k++) { tree.add(r0[k], 1); for (auto l : all[k]) res += tree.sum_right(l); } }; for (int i = 1; i + 1 < n; i++) { bool ok[n][m]; std::vector<int> max(m, -1); for (int j = i + 1; j < n; j++) { for (int k = 1; k + 1 < m; k++) { max[k] = std::max(max[k], a[j - 1][k]); ok[j][k] = max[k] < a[j][k] && max[k] < a[i - 1][k]; } } std::vector<int> cur(n - i, 0); for (int j = m - 2; j >= 1; j--) { for (int k = i + 1; k < n; k++) { if (ok[k][j]) cur[k - i]++; else cur[k - i] = 0; } calc(cur, r1[i][j]); } } } return res; } std::random_device rnd_dev; std::mt19937 rnd(rnd_dev() ^ clock()); int rnd_int(int l, int r) { return std::uniform_int_distribution<>(l, r)(rnd); } #ifdef LOCAL int main() { int n = ri(); int m = ri(); std::vector<std::vector<int> > a(n, std::vector<int>(m)); for (auto &i : a) for (auto &j : i) j = ri(); printf("%lld\n", count_rectangles(a)); { int n, m; n = m = 700; std::vector<std::vector<int> > a(n, std::vector<int>(m)); for (auto &i : a) for (auto &j : i) j = rnd_int(1, 1000000); clock_t r0 = clock(); int res = count_rectangles(a); clock_t r1 = clock(); printf("%d\n", res); printf("took %f ms\n", (double) (r1 - r0) * 1000 / CLOCKS_PER_SEC); } return 0; } #endif

Compilation message (stderr)

rect.cpp: In function 'int ri()':
rect.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
#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...