| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 656791 | jcelin | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rect.h"
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e3 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 12;
const int off = 1 << logo;
const int trsz = off << 1;
struct tournament{
int seg[trsz], type;
int merge(int a, int b){
if(type == 0) return max(a, b);
return min(a, b);
}
void build(){
for(int i=off - 1; i; i--) seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void update(int x, int val){
seg[x + off] = val;
}
int query(int x, int lo, int hi, int a, int b){
if(lo >= b or hi <= a) return inf * type - 5;
if(lo >= a and hi <= b) return seg[x];
int mid = (lo + hi) / 2;
return merge(query(x * 2, lo, mid, a, b), query(x * 2 + 1, mid, hi, a, b));
}
}h1[MAXN], h2[MAXN], h3[MAXN], h4[MAXN];
vii st;
// i j 0 - prvi veci nalijevo od (i, j)
// i j 1 - prvi veci nadesno od (i, j)
// i j 2 - prvi veci gore od (i, j)
// i j 3 - prvi veci dolje od (i, j)
int bg[MAXN][MAXN][4];
int count_rectangles(matrix mat){
int n = mat.size();
int m = mat[0].size();
REP(i, n){
st.clear();
st.PB({inf, -1});
REP(j, m){
while(st.back().X <= mat[i][j]) st.PPB();
bg[i][j][0] = st.back().Y;
st.PB({mat[i][j], j});
}
}
REP(i, n){
st.clear();
st.PB({inf, m + 1});
for(int j = m - 1; j >= 0; j--){
while(st.back().X <= mat[i][j]) st.PPB();
bg[i][j][1] = st.back().Y;
st.PB({mat[i][j], j});
}
}
REP(j, m){
st.clear();
st.PB({inf, -1});
REP(i, n){
while(st.back().X <= mat[i][j]) st.PPB();
bg[i][j][2] = st.back().Y;
st.PB({mat[i][j], i});
}
}
REP(j, m){
st.clear();
st.PB({inf, n + 1});
for(int i = n - 1; i >= 0; i--){
while(st.back().X <= mat[i][j]) st.PPB();
bg[i][j][3] = st.back().Y;
st.PB({mat[i][j], i});
}
}
REP(i, n) REP(j, m){
h1[j].update(i, bg[i][j][0]);
h2[j].update(i, bg[i][j][1]);
h3[i].update(j, bg[i][j][2]);
h4[i].update(j, bg[i][j][3]);
}
REP(i, n) h1[i].type = 0, h2[i].type = 1, h1[i].build(), h2[i].build();
REP(j, m) h3[j].type = 0, h4[j].type = 1, h3[j].build(), h4[j].build();
/*
cout << "\n";
REP(i, n){
REP(j, m){
cout << bg[i][j][3] << " ";
}
cout << "\n";
}
cout << "\n";
REP(i, n){
REP(j, m){
cout << bg[i][j][2] << " ";
}
cout << "\n";
}*/
vll good;
REP(i, n){
REP(j, m){
if(i == 0 or j == 0 or i == n - 1 or j == m - 1) continue;
if(bg[i][j][0] == -1 or bg[i][j][1] == m + 1) continue;
if(bg[i][j][2] == -1 or bg[i][j][3] == n + 1) continue;
//if(i != 2 or j != 1) continue;
//cout << i << " " << j << "\n";
//REP(k, 4) cout << bg[i][j][k] << " ";
//cout << '\n';
ll hash = 0;
REP(k, 4) hash += bg[i][j][k], hash *= MAXN;
//lijeve gr.
if(bg[i][j][0] < h1[bg[i][j][1]].query(1, 0, off, bg[i][j][2] + 1, (bg[i][j][3] - 1) + 1)) continue;
//cout << "PR1" << "\n";
//desne
if(bg[i][j][1] > h2[bg[i][j][0]].query(1, 0, off, bg[i][j][2] + 1, (bg[i][j][3] - 1) + 1)) continue;
//cout << "PR2" << "\n";
//gore
if(bg[i][j][2] < h3[bg[i][j][3]].query(1, 0, off, bg[i][j][0] + 1, (bg[i][j][1] - 1) + 1)) continue;
//cout << "PR3" << "\n";
//cout << bg[i][j][3] << " " << h4[bg[i][j][2]].query(1, 0, off, bg[i][j][0] + 1, (bg[i][j][1] - 1) + 1) << "\n";
//dolje
if(bg[i][j][3] > h4[bg[i][j][2]].query(1, 0, off, bg[i][j][0] + 1, (bg[i][j][1] - 1) + 1)) continue;
//cout << "PR4" << "\n";
//cout << "DOBARR " << i << " " << j << "\n";
//REP(k, 4) cout << bg[i][j][k] << " ";
//cout << "\n---------------\n";
good.PB(hash);
}
}
if(good.empty()) return 0;
sort(all(good));
ll pre = good[0];
int ret = 1;
for(auto &x : good) ret += (x != pre), pre = x;
return ret;
}
/*
void solve(){
int n, m;
cin >> n >> m;
matrix cur;
vi s;
s.resize(m);
REP(i, n){
for(auto &x : s) cin >> x;
cur.PB(s);
}
cout << count_rectangles(cur);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
//cin >> t;
while(t--)solve();
return 0;
}
*/