이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
struct node{
int on = 0, mxx, mnx, mxy, mny;
};
vector<vector<node>> st;
int lenx = 1, leny = 1;
node zero({1, 0, INT_MAX/2, 0, INT_MAX/2});
vector<int> get_last_big(vector<int> v){
int n = v.size();
vector<int> res(n, -1);
stack<pii> s;
s.push({INT_MAX/2, -1});
FOR(i, n){
int a = v[i];
while(a >= s.top().ff) s.pop();
res[i] = s.top().ss;
s.push({a, i});
}
return res;
}
node comb(node a, node b){
node res;
res.on = min(a.on, b.on);
res.mnx = min(a.mnx, b.mnx);
res.mny = min(a.mny, b.mny);
res.mxx = max(a.mxx, b.mxx);
res.mxy = max(a.mxy, b.mxy);
return res;
}
void updy(int y, node val, int i, int j = 1, int s = 0, int e = leny){
if(y < s || y >= e) return;
if(y == s && s + 1 == e) {
if(i >= lenx) st[i][j] = val;
else st[i][j] = comb(st[i * 2][j], st[i * 2 + 1][j]);
return;
}
updy(y, val, i, j * 2, s, (s + e) / 2);
updy(y, val, i, j * 2 + 1, (s + e) / 2, e);
st[i][j] = comb(st[i][j * 2], st[i][j * 2 + 1]);
}
void updx(int x, int y, node val, int i = 1, int s = 0, int e = lenx){
if(x < s || x >= e) return;
if(x == s && s + 1 == e) {updy(y, val, i); return;}
updx(x, y, val, i * 2, s, (s + e) / 2);
updx(x, y, val, i * 2 + 1, (s + e) / 2, e);
updy(y, val, i);
}
node qryy(int l, int r, int i, int j = 1, int s = 0, int e = leny){
if(l >= e || r <= s) return zero;
if(l <= s && e <= r) return st[i][j];
return comb(qryy(l, r, i, j * 2, s, (s + e) / 2),
qryy(l, r, i, j * 2 + 1, (s + e) / 2, e));
}
node qryx(int xl, int xr, int yl, int yr, int i = 1, int s = 0, int e = lenx){
if(xl >= e || xr <= s) return zero;
if(xl <= s && e <= xr) return qryy(yl, yr, i);
return comb(qryx(xl, xr, yl, yr, i * 2, s, (s + e) / 2),
qryx(xl, xr, yl, yr, i * 2 + 1, (s + e) / 2, e));
}
long long count_rectangles(vector<vector<signed>> v) {
int n = v.size();
while(lenx < n) lenx *= 2;
int m = v[0].size();
while(leny < m) leny *= 2;
st.assign(2 * lenx, vector<node>(2 * leny));
vector<vector<node>> passive(n, vector<node>(m));
FOR(i, n){
vector<int> cur;
vector<int> res;
FOR(j, m){
cur.push_back(v[i][j]);
}
res = get_last_big(cur);
FOR(j, m){
passive[i][j].mnx = res[j];
}
reverse(all(cur));
res = get_last_big(cur);
reverse(all(res));
FOR(j, m){
passive[i][j].mxx = m - res[j] - 1;
}
}
FOR(j, m){
vector<int> cur;
vector<int> res;
FOR(i, n){
cur.push_back(v[i][j]);
}
res = get_last_big(cur);
FOR(i, n){
passive[i][j].mny = res[i];
}
reverse(all(cur));
res = get_last_big(cur);
reverse(all(res));
FOR(i, n){
passive[i][j].mxy = n - res[i] - 1;
}
}
vector<vector<pii>> ord(7000005);
FOR(i, n) FOR(j, m){
ord[v[i][j]].push_back({i, j});
}
ll res = 0;
for (auto o : ord) {
for (auto [x, y] : o) {
passive[x][y].on = true;
updx(x, y, passive[x][y]);
int mnx = passive[x][y].mnx;
int mny = passive[x][y].mny;
int mxx = passive[x][y].mxx;
int mxy = passive[x][y].mxy;
if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue;
node ret = qryx(
mny + 1,
mxy,
mnx + 1,
mxx
);
bool f = 0;
if(!ret.on) f = 1;
if(ret.mnx < mnx) f = 1;
if(ret.mny < mny) f = 1;
if(ret.mxx > mxx) f = 1;
if(ret.mxy > mxy) f = 1;
if(!f)
res++;
}
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |