Submission #1185231

#TimeUsernameProblemLanguageResultExecution timeMemory
1185231SwanRectangles (IOI19_rect)C++20
100 / 100
2693 ms550328 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <vector> #include <stack> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <climits> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> #include <optional> //#define int long long #define INP freopen("subrev.in","r",stdin) #define OUTP freopen("subrev.out","w",stdout) using ld = long double; using LD = ld; using namespace std; vector<pair<int, int> > getGoodPairs(vector<int>& v) { vector<pair<int, int> > res; stack<pair<int, int> > s; for (int i = 0; i < v.size(); i++) { while(s.size() && v[i] > s.top().first) s.pop(); if (s.size() && abs(s.top().second - i) > 1) res.push_back({s.top().second, i}); s.push({v[i], i}); } while (s.size()) s.pop(); for (int i = v.size() - 1; i >= 0; i--) { while(s.size() && v[i] > s.top().first) s.pop(); if (s.size() && !(v[i] == s.top().first) && abs(i - s.top().second) > 1) { res.push_back({i, s.top().second}); } s.push({v[i], i}); } return res; } struct st { int r1, r2, col; st() {} st(int r1, int r2, int col) : r1(r1), r2(r2), col(col) {} bool operator<(const st& ot) const { if (make_pair(r1, r2) == make_pair(ot.r1, ot.r2)) return col < ot.col; else return make_pair(r1, r2) < make_pair(ot.r1, ot.r2); } }; const int maxn = 2600, maxm = 2600; vector<pair<int, int> > ans[maxn][maxm]; long long count_rectangles(vector<vector<int> > v) { int n = v.size(); int m = v[0].size(); vector<st> allPairs; vector<st> allPairsRows; for (int col = 0; col < m; col++) { vector<int> colVals; for (int i = 0; i < n; i++) colVals.push_back(v[i][col]); vector<pair<int, int> > pairsForCol = getGoodPairs(colVals); for (auto a : pairsForCol) allPairs.push_back(st(a.first, a.second, col)); } sort(allPairs.begin(), allPairs.end()); for (int row = 0; row < n; row++) { vector<pair<int, int> > pairsForRow = getGoodPairs(v[row]); for (auto a : pairsForRow) allPairsRows.push_back(st(a.first, a.second, row)); } sort(allPairsRows.begin(), allPairsRows.end()); int cur = 0; int r = -1; int l = 0; while (l < allPairsRows.size()) { if (r < l) { r = l; cur = 1; } pair<int, int> curPair = {allPairsRows[l].r1, allPairsRows[l].r2}; while (r + 1 < allPairsRows.size()) { pair<int, int> nextPair = {allPairsRows[r + 1].r1, allPairsRows[r + 1].r2}; if (curPair == nextPair && allPairsRows[r + 1].col - allPairsRows[r].col == 1) { r++; cur++; } else break; } ans[allPairsRows[l].col][allPairsRows[l].r1].push_back({allPairsRows[l].r2, cur}); l++; cur--; } cur = 0; r = -1; l = 0; long long res = 0; while (l < allPairs.size()) { if (r < l) { r = l; cur = 1; } pair<int, int> curPair = {allPairs[l].r1, allPairs[l].r2}; while (r + 1 < allPairs.size()) { pair<int, int> nextPair = {allPairs[r + 1].r1, allPairs[r + 1].r2}; if (curPair == nextPair && allPairs[r + 1].col - allPairs[r].col == 1) { r++; cur++; } else break; } if (allPairs[l].col == 0 || allPairs[l].col == m - 1 || allPairs[l].r2 - allPairs[l].r1 <= 1) { l++; cur--; continue; } for (auto a : ans[allPairs[l].r1 + 1][allPairs[l].col - 1]) { // cout << "W " << allPairs[l].r1 << ' ' << allPairs[l].r2 << ' ' << allPairs[l].col << endl; if (a.first <= allPairs[r].col + 1 && allPairs[l].r2 - allPairs[l].r1 - 1 <= a.second) res++; } l++; cur--; } return res; } /* void solve() { int n, m; cin >> n >> m; vector<vector<int> > v; for (int i = 0; i < n; i++) { vector<int> r; for (int j = 0; j < m; j++) { int x; cin >> x; r.push_back(x); } v.push_back(r); } cout << count_rectangles(v); } int main() { ios_base::sync_with_stdio(0); solve(); } */
#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...