Submission #843627

#TimeUsernameProblemLanguageResultExecution timeMemory
843627siewjhRectangles (IOI19_rect)C++17
100 / 100
2909 ms1004852 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2505; int rows, cols; ll fw[MAXN]; vector<int> prs[MAXN][MAXN]; vector<pair<int, int>> lrc[MAXN][MAXN], tbc[MAXN][MAXN]; void update(int x, ll v){ while (x < cols){ fw[x] += v; x += (x & (-x)); } } void rupdate(int x, int y, ll v){ update(x, v); update(y + 1, -v); } ll query(int x){ ll ans = 0; while (x){ ans += fw[x]; x -= (x & (-x)); } return ans; } ll count_rectangles(vector<vector<int>> a) { rows = a.size(), cols = a[0].size(); for (int i = 0; i < rows; i++){ stack<int> s; for (int j = 0; j < cols; j++){ while (!s.empty() && a[i][j] > a[i][s.top()]) s.pop(); if (!s.empty() && s.top() + 1 != j) prs[s.top()][j].push_back(i); s.push(j); } while (!s.empty()) s.pop(); for (int j = cols - 1; j >= 0; j--){ bool same = false; while (!s.empty() && a[i][j] >= a[i][s.top()]){ if (a[i][j] == a[i][s.top()]) same = true; s.pop(); } if (!same && !s.empty() && s.top() - 1 != j) prs[j][s.top()].push_back(i); s.push(j); } } for (int i = 0; i < cols; i++) for (int j = i + 2; j < cols; j++){ int sz = prs[i][j].size(); for (int s = 0; s < sz; s++){ int e = s; while (e != sz - 1 && prs[i][j][e + 1] == prs[i][j][e] + 1) e++; for (int k = s; k <= e; k++) lrc[prs[i][j][k]][i + 1].push_back({prs[i][j][e], j - 1}); s = e; } } for (int j = 0; j < cols; j++){ stack<int> s; for (int i = 0; i < rows; i++){ while (!s.empty() && a[i][j] > a[s.top()][j]) s.pop(); if (!s.empty() && s.top() + 1 != i) prs[i][s.top()].push_back(j); s.push(i); } for (int i = rows - 1; i >= 0; i--){ bool same = 0; while (!s.empty() && a[i][j] >= a[s.top()][j]){ if (a[i][j] == a[s.top()][j]) same = 1; s.pop(); } if (!same && !s.empty() && s.top() - 1 != i) prs[s.top()][i].push_back(j); s.push(i); } } for (int i = 0; i < rows; i++) for (int j = i + 2; j < rows; j++){ int sz = prs[j][i].size(); for (int s = 0; s < sz; s++){ int e = s; while (e != sz - 1 && prs[j][i][e + 1] == prs[j][i][e] + 1) e++; for (int k = s; k <= e; k++) tbc[i + 1][prs[j][i][k]].push_back({j - 1, prs[j][i][e]}); s = e; } } ll ans = 0; for (int i = 1; i < rows - 1; i++) for (int j = 1; j < cols - 1; j++){ sort(lrc[i][j].begin(), lrc[i][j].end()); sort(tbc[i][j].begin(), tbc[i][j].end()); int ind = 0; for (auto p : lrc[i][j]){ int r, c; tie(r, c) = p; while (ind != tbc[i][j].size() && tbc[i][j][ind].first <= r){ rupdate(1, tbc[i][j][ind].second, 1); ind++; } ans += query(c); } for (int k = 0; k < ind; k++) rupdate(1, tbc[i][j][k].second, -1); } return ans; }

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     while (ind != tbc[i][j].size() && tbc[i][j][ind].first <= r){
      |            ~~~~^~~~~~~~~~~~~~~~~~~
#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...