| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 372350 | jainbot27 | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
ll count_rectangles(vector<vi> a){
int n = siz(a), m = siz(a[0]); ll ans = 0;
auto precalc = [&](vector<vi> b){
int N = siz(b), M = siz(b[0]);
auto go = [&](vi v){
stack<pii> s;
vi res(M);
F0R(i, M){
while(siz(s)&&s.top().f<v[i]){
s.pop();
}
if(!siz(s)) res[i]=-1;
else res[i]=s.top().s;
s.push({v[i], i});
}
return res;
};
vector<vector<map<int, int>>> res(N, vector<map<int, int>>(M));
F0R(i, N){
vi l = go(b[i]);
reverse(all(b[i]));
vi r = go(b[i]);
reverse(all(b[i]));
reverse(all(r));
F0R(j, M){
if(r[j]!=-1) r[j]=M-1-r[j];
}
F0R(j, M){
if(l[j]!=-1&&l[j]!=j-1){
//res[i][j-1].pb({l[j]+1, 1});
res[i][j-1][l[j]+1]=1;
}
}
F0R(j, M){
if(r[j]!=-1&&r[j]!=j+1){
//res[i][r[j]-1].pb({j+1, 1});
res[i][r[j]-1][j+1]=1;
}
}
//F0R(j, M){
// sort(all(res[i][j]));
// res[i][j].resize(unique(all(res[i][j]))-res[i][j].begin());
//}
}
F0R(i, N-1){
F0R(j, M){
trav(x, res[i][j]){
if(res[i+1][j].count(x.f)){
res[i+1][j][x.f]++;
}
}
}
}
return res;
};
vector<vector<map<int, int>>> X = precalc(a);
vector<vi> c(m, vi(n));
F0R(i, n)
F0R(j, m)
c[j][i]=a[i][j];
vector<vector<map<int, int>>> Y2 = precalc(c);
vector<vector<map<int, int>>> Y(n, vector<map<int, int>>(m));
F0R(i, n)
F0R(j, m)
Y[i][j]=Y2[j][i];
vector<vector<vpii>> x, y;
x = y = vector<vector<vpii>>(n, vector<vpii>(m));
F0R(i, n){
F0R(j, m){
for(auto Q : X[i][j]){
pair<int, int> V = Q;
x[i][j].pb(V);
}
for(auto Q : Y[i][j]){
pair<int, int> V = Q;
y[i][j].pb(V);
}
}
}
F0R(i, n){
F0R(j, m){
trav(v, x[i][j]){
trav(v2, y[i][j]){
if(v.s>=i-v2.f+1&&v2.s>=j-v.f+1) {
ans++;
}
}
}
}
}
return ans;
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N, M; cin >> N >> M;
vector<vi> inp(N, vi(M));
F0R(i, N){
F0R(j, M){
cin >> inp[i][j];
}
}
cout << count_rectangles(inp) << nl;
return 0;
}