제출 #826037

#제출 시각아이디문제언어결과실행 시간메모리
826037JosiaRectangles (IOI19_rect)C++17
59 / 100
5070 ms677108 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> A; vector<vector<int>> AT; int N, M; struct seg { vector<int> tree; bool minmax; int neut; int op(int a, int b) { if (minmax) return max(a,b); return min(a,b); } void update(int v, int rl, int rr, int pos, int x) { if (rl == rr) { tree[v] = x; return; } int rm = (rl + rr)/2; if (pos <= rm) update(v*2, rl, rm, pos, x); else update(v*2+1, rm+1, rr, pos, x); tree[v] = op(tree[v*2], tree[v*2+1]); } int query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return neut; if (rl == ql && rr == qr) return tree[v]; int rm = (rl + rr) / 2; return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr)); } void init(int n, vector<int> a, bool type) { minmax = type; if (type) neut = -1e9; else neut = 1e9; tree.assign(n*4, 0); for (int i = 0; i<n; i++) update(1, 0, n-1, i, a[i]); } }; vector<vector<array<int, 4>>> howFar; // 1,0; 0,1; -1,0; 0,-1; vector<vector<array<int, 4>>> howFarT; // 1,0; 0,1; -1,0; 0,-1; void makeHowFar() { howFar.assign(N, vector<array<int, 4>>(M)); for (int i = 0; i<N; i++) { set<pair<int, int>> s; for (int j = 0; j<M; j++) { while (s.size() && (*s.begin()).first <= A[i][j]) { howFar[i][(*s.begin()).second][1] = j; s.erase(s.begin()); } s.insert({A[i][j], j}); } for (auto aa: s) { howFar[i][aa.second][1] = M-1; } } for (int i = 0; i<M; i++) { set<pair<int, int>> s; for (int j = 0; j<N; j++) { while (s.size() && (*s.begin()).first <= AT[i][j]) { howFar[(*s.begin()).second][i][0] = j; s.erase(s.begin()); } s.insert({AT[i][j], j}); } for (auto aa: s) { howFar[aa.second][i][0] = N-1; } } for (int i = 0; i<N; i++) { set<pair<int, int>> s; for (int j = M-1; j>=0; j--) { while (s.size() && (*s.begin()).first <= A[i][j]) { howFar[i][(*s.begin()).second][3] = j; s.erase(s.begin()); } s.insert({A[i][j], j}); } for (auto aa: s) { howFar[i][aa.second][3] = 0; } } for (int i = 0; i<M; i++) { set<pair<int, int>> s; for (int j = N-1; j>=0; j--) { while (s.size() && (*s.begin()).first <= AT[i][j]) { howFar[(*s.begin()).second][i][2] = j; s.erase(s.begin()); } s.insert({AT[i][j], j}); } for (auto aa: s) { howFar[aa.second][i][2] = 0; } } } vector<seg> howFar10, howFar01, howFar_10, howFar0_1; void makeHowFarSegs() { howFar10.resize(N); for (int i = 0; i<N; i++) { vector<int> a(M); for (int j = 0; j<M; j++) a[j] = howFar[i][j][0]; howFar10[i].init(M, a, 0); } howFar01.resize(M); for (int i = 0; i<M; i++) { vector<int> a(N); for (int j = 0; j<N; j++) a[j] = howFarT[i][j][1]; howFar01[i].init(N, a, 0); } howFar_10.resize(N); for (int i = 0; i<N; i++) { vector<int> a(M); for (int j = 0; j<M; j++) a[j] = howFar[i][j][2]; howFar_10[i].init(M, a, 1); } howFar0_1.resize(M); for (int i = 0; i<M; i++) { vector<int> a(N); for (int j = 0; j<N; j++) a[j] = howFarT[i][j][3]; howFar0_1[i].init(N, a, 1); } } bool verify(int top, int bottom, int left, int right) { // top, bottom, left, right if (bottom-top < 2) return 0; if (right-left < 2) return 0; if(!(howFar10[top].query(1, 0, M-1, left+1, right-1) >= bottom)) return 0; if(!(howFar_10[bottom].query(1, 0, M-1, left+1, right-1) <= top)) return 0; if(!(howFar01[left].query(1, 0, N-1, top+1, bottom-1) >= right)) return 0; if(!(howFar0_1[right].query(1, 0, N-1, top+1, bottom-1) <= left)) return 0; return 1; } vector<array<int,4>> candidates; void makeCandidates() { candidates.resize((N-1)*(M-1)*8); int cnt = 0; for (int i = 1; i<N-1; i++) { for (int j = 1; j<M-1; j++) { int left = howFar[i][j+1][3], right = howFar[i][j-1][1]; int top = howFar[i+1][j][2], bottom = howFar[i-1][j][0]; int leftTop = howFar[i+1][left+1][2], leftBottom = howFar[i-1][left+1][0]; int rightTop = howFar[i+1][right-1][2], rightBottom = howFar[i-1][right-1][0]; candidates[cnt] = {top, i+1, left, j+1}; cnt++; candidates[cnt] = {leftTop, i+1, left, j+1}; cnt++; candidates[cnt] = {top, i+1, j-1, right}; cnt++; candidates[cnt] = {rightTop, i+1, j-1, right}; cnt++; candidates[cnt] = {i-1, bottom, left, j+1}; cnt++; candidates[cnt] = {i-1, leftBottom, left, j+1}; cnt++; candidates[cnt] = {i-1, bottom, j-1, right}; cnt++; candidates[cnt] = {i-1, rightBottom, j-1, right}; cnt++; } } } long long count_rectangles(std::vector<std::vector<int> > _a) { cerr << "start\n"; A = _a; N = A.size(); M = A[0].size(); AT.assign(M, vector<int>(N, 0)); for (int i = 0; i<N; i++) { for (int j = 0; j<M; j++) { AT[j][i] = A[i][j]; } } makeHowFar(); howFarT.assign(M, vector<array<int,4>>(N)); for (int i = 0; i<N; i++) { for (int j = 0; j<M; j++) { howFarT[j][i] = howFar[i][j]; } } cerr << "madehowfar\n"; makeHowFarSegs(); cerr << "madesegs\n"; int res = 0; makeCandidates(); cerr << "madecands\n"; sort(candidates.begin(), candidates.end()); candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end()); for (auto i: candidates) { res += verify(i[0], i[1], i[2], i[3]); } 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...