Submission #725165

#TimeUsernameProblemLanguageResultExecution timeMemory
725165dooompyRectangles (IOI19_rect)C++17
100 / 100
2848 ms595556 KiB
#include "bits/stdc++.h" #include "rect.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("{" + string(#args) + "}", args) #else #define test(args...) void(0) #endif using ll = long long; int lft[2505][2505]; int rht[2505][2505]; vector<pair<int, int>> interval[2505]; vector<pair<int, int>> otherrow[2505][2505]; struct segment { int l, r, last; bool operator<(segment o) const { return l < o.l; } }; vector<segment> row[2505]; int bit[2505][2505]; void update(int id, int pos, int val) { for (; pos < 2505; pos += pos & -pos) { bit[id][pos] += val; } } int query(int id, int pos) { int sum = 0; for (; pos; pos -= pos & -pos) { sum += bit[id][pos]; } return sum; } ll count_rectangles(vector<vector<int>> a) { int n = a.size(); int m= a[0].size(); if (min(n, m) <= 2) { return 0; } deque<int> dq; memset(lft, -1, sizeof(lft)); memset(rht, -1, sizeof(rht)); for (int i = 1; i <= n - 2; i++) { while (!dq.empty()) dq.pop_back(); for (int j = 0; j < m; j++) { while (!dq.empty() && a[i][j] > a[i][dq.back()]) dq.pop_back(); if (!dq.empty() && dq.back() != j-1) { lft[i][j] = dq.back(); interval[i].push_back({dq.back(), j}); } dq.push_back(j); } while (!dq.empty()) dq.pop_back(); for (int j = m - 1; j >= 0; j--) { while (!dq.empty() && a[i][j] > a[i][dq.back()]) dq.pop_back(); if (!dq.empty() && dq.back() != j+1) { rht[i][j] = dq.back(); interval[i].push_back({j, dq.back()}); } dq.push_back(j); } } for (int i = 1; i <= n-2; i++) { for (auto [l, r] : interval[i]) { if (lft[i][r] != l && rht[i][l] != r) continue; if (lft[i][r] == l) lft[i][r] = -1; if (rht[i][l] == r) rht[i][l] = -1; int nxt = i + 1; while (nxt <= n - 2 && (lft[nxt][r] == l || rht[nxt][l] == r)) { if (lft[nxt][r] == l) lft[nxt][r] = -1; if (rht[nxt][l] == r) rht[nxt][l] = -1; nxt++; } for (int j = i; j < nxt; j++) { row[j].push_back({l + 1, r - 1, nxt - 1}); } } sort(row[i].begin(), row[i].end()); } memset(lft,-1,sizeof(lft)); memset(rht,-1,sizeof(rht)); for (int i = 1; i <= m - 2; i++) { while (!dq.empty()) dq.pop_back(); for (int j = 0; j < n; j++) { while (!dq.empty() && a[j][i] > a[dq.back()][i]) dq.pop_back(); if (!dq.empty() && dq.back() != j-1) { lft[i][j] = dq.back(); interval[i].push_back({dq.back(), j}); } dq.push_back(j); } while (!dq.empty()) dq.pop_back(); for (int j = n - 1; j >= 0; j--) { while (!dq.empty() && a[j][i] > a[dq.back()][i]) dq.pop_back(); if (!dq.empty() && dq.back() != j+1) { rht[i][j] = dq.back(); interval[i].push_back({j, dq.back()}); } dq.push_back(j); } } for (int i = 1; i <= m - 2; i++) { for (auto [l, r] : interval[i]) { if (lft[i][r] != l && rht[i][l] != r) continue; if (lft[i][r] == l) lft[i][r] = -1; if (rht[i][l] == r) rht[i][l] = -1; int nxt = i + 1; while (nxt <= m - 2 && (lft[nxt][r] == l || rht[nxt][l] == r)) { if (lft[nxt][r] == l) lft[nxt][r] = -1; if (rht[nxt][l] == r) rht[nxt][l] = -1; nxt++; } for (int j = i; j < nxt; j++) { otherrow[l + 1][i].emplace_back(j, r - 1); } } } ll ans = 0; for (int i = 1; i <= n - 2; i++) { int cur = 1; vector<pair<int, int>> ops; for (auto [l, r, last] : row[i]) { while (cur <= l) { for (auto [col, lastrow] : otherrow[i][cur]) { update(col, lastrow, 1); ops.push_back({col, lastrow}); } cur++; } ans += query(r, last); } while (!ops.empty()) { auto [col, lastrow] = ops.back(); ops.pop_back(); update(col, lastrow, -1); } } return ans; } //int main() { // ios_base::sync_with_stdio(0); // cin.tie(0); cout.tie(0); //// freopen("", "r", stdin); //// freopen("", "w", stdout); // cout << count_rectangles({{4, 8, 7, 5, 6}, // {7, 4, 10, 3, 5}, // {9, 7, 20, 14, 2}, // {9, 14, 7, 3, 6}, // {5, 7, 5, 2, 7}, // {4, 5, 13, 5, 6}}); //}
#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...