제출 #1103882

#제출 시각아이디문제언어결과실행 시간메모리
1103882_8_8_Rectangles (IOI19_rect)C++17
0 / 100
3136 ms480584 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2500 + 12; int n, m, a[N][N], it[N][N]; vector<array<int, 2>> r[N]; vector<int> id[N][N], t[N][N], f[N][N]; int c[N][N]; void upd(int x, int y, int val) { c[x][y] += val; // while(x <= m) { // int j = y; // while(j <= m) { // c[x][j] += val; // j += j & -j; // } // x += x & -x; // } } int get(int x, int y) { // for() int ret = 0; while(x) { int j = y; while(j) { ret += c[x][j]; j -= j & -j; } x -= x & -x; } return ret; } int get(int x, int y, int x1, int y1) { int ret = 0; for(int i = x; i <= x1; i++) { for(int j = y; j <= y1; j++) { ret += c[i][j]; } } return ret; return get(x1, y1) - get(x - 1, y1) - get(x1, y - 1) + get(x - 1, y - 1); } void prec() { for(int i = 2; i < n; i++) { vector<int> st; for(int j = 1; j <= m; j++) { while(!st.empty() && a[i][st.back()] < a[i][j]) { st.pop_back(); } if(!st.empty()) { int l = st.back(); if(l + 1 <= j - 1) { r[i].push_back({l + 1, j - 1}); } } st.push_back(j); } st.clear(); for(int j = m; j >= 1; j--) { while(!st.empty() && a[i][st.back()] < a[i][j]) { st.pop_back(); } if(!st.empty()) { int l = st.back(); if(j + 1 <= l - 1) { r[i].push_back({j + 1, l - 1}); } } st.push_back(j); } sort(r[i].begin(), r[i].end()); r[i].resize(unique(r[i].begin(), r[i].end()) - r[i].begin()); for(auto [l, r]:r[i]) { id[l][r].push_back(i); } } for(int j = 2; j < m; j++) { vector<int> st; for(int i = 1; i <= n; i++) { while(!st.empty() && a[st.back()][j] < a[i][j]) { st.pop_back(); } if(!st.empty()) { int l = st.back(); if(l + 1 <= i - 1) { t[l + 1][j].push_back(i - 1); } } st.push_back(i); } st.clear(); for(int i = n; i >= 1; i--) { while(!st.empty() && a[st.back()][j] < a[i][j]) { st.pop_back(); } if(!st.empty()) { int l = st.back(); if(l - 1 >= i + 1) { t[i + 1][j].push_back(l - 1); } } st.push_back(i); } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { sort(t[i][j].begin(), t[i][j].end()); t[i][j].resize(unique(t[i][j].begin(), t[i][j].end()) - t[i][j].begin()); } } for(int i = 1; i <= m; i++) { for(int j = i; j <= m; j++) { f[i][j].resize((int)id[i][j].size()); for(int k = 0; k < (int)f[i][j].size(); k++) { if(k && id[i][j][k] - 1 == id[i][j][k - 1]) { f[i][j][k] = f[i][j][k - 1]; } else { int it = k + 1; while(it < (int)id[i][j].size() && id[i][j][it] - 1 == id[i][j][it - 1]) { it++; } it--; f[i][j][k] = id[i][j][it]; } } } } } ll solve() { ll res = 0; for(int i = 2; i < n; i++) { vector<array<int, 2>> pt; for(int j = 2; j < m; j++) { for(int f:t[i][j]) { pt.push_back({f, j}); } } sort(pt.begin(), pt.end()); vector<array<int, 3>> s; for(int i = 0; i < (int)pt.size(); ) { int j = i + 1; while(j < (int)pt.size() && pt[j][0] == pt[j - 1][0] && pt[j][1] == pt[j - 1][1] + 1) { j++; } s.push_back({pt[i][0], pt[i][1], pt[j - 1][1]}); i = j; } sort(s.begin(), s.end()); sort(r[i].begin(), r[i].end(), [&](array<int, 2> x, array<int, 2> y){ return f[x[0]][x[1]][it[x[0]][x[1]]] < f[y[0]][y[1]][it[y[0]][y[1]]]; }); int ti = 0; for(auto [l, r]:r[i]) { while(ti < (int)s.size() && s[ti][0] <= f[l][r][it[l][r]]) { upd(s[ti][1], s[ti][2], 1); ti++; } res += get(1, l, r, m); // for(int j = 0; j < ti; j++) { // if(s[j][1] <= l && s[j][2] >= r) { // res++; // } // } } memset(c, 0, sizeof(c)); for(int j = 0; j < ti; j++) { upd(s[j][1], s[j][2], -1); } for(auto [l, r]:r[i]) { it[l][r]++; } } return res; } ll count_rectangles(vector<vector<int> > _A) { n = (int)_A.size(); m = (int)_A[0].size(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { a[i][j] = _A[i - 1][j - 1]; } } prec(); return 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...