이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
struct Fenwick{
vector < int > tree;
int tree_len;
Fenwick(int len){
tree_len = len;
tree.assign(len + 5 , 0);
}
int pref_sum(int p){
int ret = 0;
while(p > 0){
ret += tree[p];
p -= p & (-p);
}
return ret;
}
int query(int l , int r){
return pref_sum(r) - pref_sum(l-1);
}
void update(int p , int x){
while(p <= tree_len){
tree[p] += x;
p += p & (-p);
}
}
};
long long count_rectangles(vector<vector<int> > a) {
int n = sz(a) , m = sz(a[0]);
int nxt_right[n][m] , nxt_down[n][m];
memset(nxt_right , -1 , sizeof(nxt_right));
memset(nxt_down , -1 , sizeof(nxt_down));
for(int i = 0;i<n;i++){
stack < int > st;
for(int j = m-1;j>=0;j--){
while(sz(st) and a[i][st.top()] <= a[i][j])st.pop();
if(sz(st))nxt_right[i][j] = st.top();
st.push(j);
}
}
for(int j = 0;j<m;j++){
stack < int > st;
for(int i = n-1;i>=0;i--){
while(sz(st) and a[st.top()][j] <= a[i][j])st.pop();
if(sz(st))nxt_down[i][j] = st.top();
st.push(i);
}
}
vector < pair < int , int > > ranges_right[n][m] , ranges_down[n][m];
for(int i = n-1;i>=0;i--){
for(int j = m-1;j>=0;j--){
// going to right
int cury = j+1;
while(cury < m and a[i][j] > a[i][cury]){
cury = nxt_right[i][cury];
if(cury == -1)break;
else if(i != n-1){
int ptr = lower_bound(all(ranges_right[i+1][j]) , pair<int,int>{cury , 0}) - ranges_right[i+1][j].begin();
if(ptr < sz(ranges_right[i+1][j]) and cury == ranges_right[i+1][j][ptr].first){
ranges_right[i][j].push_back({cury , ranges_right[i+1][j][ptr].second});
}
else{
ranges_right[i][j].push_back({cury , i+1});
}
}
else{
ranges_right[i][j].push_back({cury , i+1});
}
}
// going to down
int curx = i+1;
while(curx < n and a[i][j] > a[curx][j]){
curx = nxt_down[curx][j];
if(curx == -1)break;
else if(j != m-1){
int ptr = lower_bound(all(ranges_down[i][j+1]) , pair<int,int>{curx , 0}) - ranges_down[i][j+1].begin();
if(ptr < sz(ranges_down[i][j+1]) and curx == ranges_down[i][j+1][ptr].first){
ranges_down[i][j].push_back({curx , ranges_down[i][j+1][ptr].second});
}
else{
ranges_down[i][j].push_back({curx , j+1});
}
}
else{
ranges_down[i][j].push_back({curx , j+1});
}
}
}
}
long long ans = 0;
for(int i = 0;i<n-1;i++){
for(int j = 0;j<m-1;j++){
sort(all(ranges_right[i+1][j]) , [&](pair < int , int > &a , pair < int , int > &b){
if(a.second < b.second)return true;
else if(a.second > b.second)return false;
else return a.first < b.first;
});
sort(all(ranges_down[i][j+1]));
Fenwick fen(max(n , m));
int lp = 0;
// cout << i << " " << j << endl;
// cout << "ranges_right : ";for(auto itr : ranges_right[i+1][j])cout << itr.first << "," << itr.second << " ";cout << endl;
// cout << "ranges_down : ";for(auto itr : ranges_down[i][j+1])cout << itr.first << "," << itr.second << " ";cout << endl;
long long locans = 0;
for(auto itr : ranges_right[i+1][j]){
while(lp < sz(ranges_down[i][j+1]) and ranges_down[i][j+1][lp].first <= itr.second){
fen.update(ranges_down[i][j+1][lp].second , 1);
lp++;
}
locans += fen.query(itr.first , max(n,m));
}
// cout << "locans : " << locans << endl;
ans += locans;
}
}
return ans;
}
# | 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... |