제출 #296644

#제출 시각아이디문제언어결과실행 시간메모리
296644Osama_AlkhodairyRectangles (IOI19_rect)C++17
72 / 100
5108 ms1007784 KiB
#include <bits/stdc++.h> #include "rect.h" //~ #include "grader.cpp" using namespace std; #define ll long long const int N = 2501; const int INF = (int)1e9; struct segment{ int tree[4 * N]; segment(){ for(int i = 0 ; i < 4 * N ; i++){ tree[i] = -INF; } } void build(int l, int r, int node, vector <int> &a, int b){ if(l == r){ if(a[l] != -1){ tree[node] = a[l] * b; } return; } int mid = (l + r) / 2; build(l, mid, 2 * node, a, b); build(mid + 1, r, 2 * node + 1, a, b); tree[node] = max(tree[2 * node], tree[2 * node + 1]); } int query(int l, int r, int node, int s, int e){ if(r < l || r < s || l > e) return -INF; if(s <= l && r <= e) return tree[node]; int mid = (l + r) / 2; return max(query(l, mid, 2 * node, s, e), query(mid + 1, r, 2 * node + 1, s, e)); } }; int n, m, vis[N * N]; vector <vector <int> > a; vector <vector <int> > us, rs, ds, ls, ue, re, de, le; vector <segment> ue_tree, re_tree, de_tree, le_tree; vector <int> v[N * N]; vector <int> calc(vector <int> &a, int b, int c){ //~ b = 0 for > //~ b = 1 for >= //~ c = 0 for forward //~ c = 1 for backward int n = a.size(); vector <int> inds; for(int i = 0 ; i < n ; i++){ if(c == 0) inds.push_back(i); else inds.push_back(n - i - 1); } vector <int> ret(n); vector <int> cur; for(auto &i : inds){ while(cur.size() && a[i] >= a[cur.back()] + b){ cur.pop_back(); } if(cur.size() == 0) ret[i] = -1; else ret[i] = cur.back(); cur.push_back(i); } return ret; } void add(int r1, int c1, int r2, int c2){ if(r1 == -1 || c1 == -1 || r2 == -1 || c2 == -1) return; v[r1 * m + c1].push_back(r2 * m + c2); } bool check(int r1, int c1, int r2, int c2){ int v = -de_tree[r1].query(0, m - 1, 1, c1 + 1, c2 - 1); if(v < r2) return 0; v = ue_tree[r2].query(0, m - 1, 1, c1 + 1, c2 - 1); if(v > r1) return 0; v = -re_tree[c1].query(0, n - 1, 1, r1 + 1, r2 - 1); if(v < c2) return 0; v = le_tree[c2].query(0, n - 1, 1, r1 + 1, r2 - 1); if(v > c1) return 0; return 1; } long long count_rectangles(std::vector<std::vector<int> > A) { a = A; n = a.size(); m = a[0].size(); us.resize(n, vector <int>(m)); ue.resize(n, vector <int>(m)); ds.resize(n, vector <int>(m)); de.resize(n, vector <int>(m)); ls.resize(n, vector <int>(m)); le.resize(n, vector <int>(m)); rs.resize(n, vector <int>(m)); re.resize(n, vector <int>(m)); ue_tree.resize(n); de_tree.resize(n); le_tree.resize(m); re_tree.resize(m); for(int i = 0 ; i < n ; i++){ vector <int> cur = a[i]; ls[i] = calc(cur, 0, 0); le[i] = calc(cur, 1, 0); rs[i] = calc(cur, 0, 1); re[i] = calc(cur, 1, 1); } for(int j = 0 ; j < m ; j++){ vector <int> cur(n); for(int i = 0 ; i < n ; i++){ cur[i] = a[i][j]; } vector <int> g; g = calc(cur, 0, 0); for(int i = 0 ; i < n ; i++){ us[i][j] = g[i]; } g = calc(cur, 1, 0); for(int i = 0 ; i < n ; i++){ ue[i][j] = g[i]; } g = calc(cur, 0, 1); for(int i = 0 ; i < n ; i++){ ds[i][j] = g[i]; } g = calc(cur, 1, 1); for(int i = 0 ; i < n ; i++){ de[i][j] = g[i]; } } for(int i = 0 ; i < n ; i++){ ue_tree[i].build(0, m - 1, 1, ue[i], 1); de_tree[i].build(0, m - 1, 1, de[i], -1); } for(int j = 0 ; j < m ; j++){ vector <int> cur(n); for(int i = 0 ; i < n ; i++){ cur[i] = le[i][j]; } le_tree[j].build(0, n - 1, 1, cur, 1); cur.assign(n, 0); for(int i = 0 ; i < n ; i++){ cur[i] = re[i][j]; } re_tree[j].build(0, n - 1, 1, cur, -1); } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ add(us[i][j], ls[i][j], ds[i][j], rs[i][j]); } } int ret = 0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ for(auto &k : v[i * m + j]){ if(vis[k]) continue; vis[k] = 1; ret += check(i, j, k / m, k % m); } for(auto &k : v[i * m + j]){ vis[k] = 0; } } } return ret; }
#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...