Submission #956687

#TimeUsernameProblemLanguageResultExecution timeMemory
956687MackerRectangles (IOI19_rect)C++17
0 / 100
110 ms165212 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; #define ff first #define ss second #define all(v) v.begin(), v.end() #define FOR(i, n) for (int i = 0; i < n; i++) struct node{ int on = 0, mxx, mnx, mxy, mny; }; vector<vector<node>> st; vector<int> get_last_big(vector<int> v){ int n = v.size(); vector<int> res(n, -1); stack<pii> s; s.push({INT_MAX, -1}); FOR(i, n){ int a = v[i]; while(a >= s.top().ff) s.pop(); res[i] = s.top().ss; s.push({a, i}); } return res; } long long count_rectangles(vector<vector<int>> v) { int n = v.size(); int m = v[0].size(); st.assign(n, vector<node>(m)); FOR(i, n){ vector<int> cur; vector<int> res; FOR(j, m){ cur.push_back(v[i][j]); } res = get_last_big(cur); FOR(j, m){ st[i][j].mnx = res[j]; } reverse(all(cur)); res = get_last_big(cur); reverse(all(res)); FOR(j, m){ st[i][j].mxx = m - res[j] - 1; } } FOR(i, m){ vector<int> cur; vector<int> res; FOR(j, n){ cur.push_back(v[j][i]); } res = get_last_big(cur); FOR(j, n){ st[j][i].mny = res[j]; } reverse(all(cur)); res = get_last_big(cur); reverse(all(res)); FOR(j, n){ st[j][i].mxy = n - res[j] - 1; } } vector<vector<pii>> ord(7000005); FOR(i, n) FOR(j, m){ ord[v[i][j]].push_back({i, j}); } ll res = 0; for (auto o : ord) { for (auto [x, y] : o) { st[x][y].on = true; } for (auto [x, y] : o) { int mxx, mnx, mxy, mny; mxx = st[x][y].mxx; mnx = st[x][y].mnx; mxy = st[x][y].mxy; mny = st[x][y].mny; if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue; bool f = 0; for (int i = mny; i <= mxy; i++){ for (int j = mnx; j <= mxx; j++) { if(!st[x][y].on) {f = 1; break;} if(st[x][y].mnx < mnx) {f = 1; break;} if(st[x][y].mny < mny) {f = 1; break;} if(st[x][y].mxx > mxx) {f = 1; break;} if(st[x][y].mxy > mxy) {f = 1; break;} } if(f) break; } if(!f) res++; } } return res; }
#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...