#include "rect.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define ln "\n"
constexpr ll inf = (1ll<<30);
/*
constexpr ll LOG = 12;
ll left_table[2510][2510][LOG+1];
ll right_table[2510][2510][LOG+1];
ll up_table[2510][2510][LOG+1];
ll down_table[2510][2510][LOG+1];*/
struct binary_indexed_tree{
vi node;
ll N;
binary_indexed_tree(int n): N(n){
node.resize(N+1);
}
void add(ll idx, ll val){
idx++;
for(; idx<=N; idx+=(idx&-idx)) node[idx] += val;
}
ll sum(ll idx){
idx++;
ll ret = 0;
for(; 0<idx; idx-=(idx&-idx)) ret += node[idx];
return ret;
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
ll H = a.size(), W = a[0].size();
long long ans = 0;
vector<vector<vector<pii>>> query(H,vector<vector<pii>>(W));
{
vii dp_right(W,vi(W));
vii right(W,vi(W));
vii rem(W);
vii new_rem(W);
per(i,H-1,0){
std::deque<ll> max, idx;
max.pb(inf);
idx.pb(-1);
rep(j,0,W){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
if(idx[0] != -1){
right[idx[0]][j] = 1;
new_rem[idx[0]].pb(j);
}
max.emplace_front(a[i][j]);
idx.emplace_front(j);
}
max.clear();
idx.clear();
max.pb(inf);
idx.pb(W);
per(j,W-1,0){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
if(idx[0] != W && a[i][j] != max[0]){
right[j][idx[0]] = 1;
new_rem[j].pb(idx[0]);
}
max.emplace_front(a[i][j]);
idx.emplace_front(j);
}
rep(j,0,W){
right[j][j+1] = 0;
for(auto el: new_rem[j]){
if(el == j+1) continue;
right[j][el] += dp_right[j][el];
}
}
rep(j,1,W-1){
for(auto el: new_rem[j-1]){
if(el == j) continue;
ll bottom = i+right[j-1][el];
// bottom 以下 かつ
ll lasting = el-j;
// lasting 以上
query[i][j].pb(mp(lasting, -bottom));
}
}
rep(j,0,W){
for(auto el: rem[j]) dp_right[j][el] = 0;
for(auto el: new_rem[j]){
dp_right[j][el] = right[j][el];
right[j][el] = 0;
}
rem[j] = new_rem[j];
new_rem[j].clear();
}
}
}
{
vii dp_down(H,vi(H));
vii down(H,vi(H));
vii rem(H);
vii new_rem(H);
per(j,W-1,0){
std::deque<ll> max, idx;
max.pb(inf);
idx.pb(-1);
rep(i,0,H){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
if(idx[0] != -1){
down[idx[0]][i] = 1;
new_rem[idx[0]].pb(i);
}
max.emplace_front(a[i][j]);
idx.emplace_front(i);
}
max.clear();
idx.clear();
max.pb(inf);
idx.pb(H);
per(i,H-1,0){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
if(idx[0] != H && a[i][j] != max[0]){
down[i][idx[0]] = 1;
new_rem[i].pb(idx[0]);
}
max.emplace_front(a[i][j]);
idx.emplace_front(i);
}
rep(i,0,H){
down[i][i+1] = 0;
for(auto el: new_rem[i]){
if(el == i+1) continue;
down[i][el] += dp_down[i][el];
}
}
rep(i,1,H-1){
for(auto el: new_rem[i-1]){
if(el == i) continue;
query[i][j].pb(mp(down[i-1][el], el));
}
}
rep(i,0,H){
for(auto el: rem[i]) dp_down[i][el] = 0;
for(auto el: new_rem[i]){
dp_down[i][el] = down[i][el];
down[i][el] = 0;
}
rem[i] = new_rem[i];
new_rem[i].clear();
}
}
}
binary_indexed_tree bit(H+10);
rep(i,1,H-1){
rep(j,1,W-1){
auto query_ = query[i][j];
sort(all(query_));
reverse(all(query_));
for(auto el: query_){
if(el.second < 0) ans += bit.sum(-el.second);
else bit.add(el.second,1);
}
for(auto el: query_){
if(el.second > 0) bit.add(el.second,-1);
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
50132 KB |
Output is correct |
| 2 |
Correct |
15 ms |
36308 KB |
Output is correct |
| 3 |
Correct |
20 ms |
49892 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
28 ms |
50004 KB |
Output is correct |
| 6 |
Correct |
23 ms |
50004 KB |
Output is correct |
| 7 |
Correct |
26 ms |
50004 KB |
Output is correct |
| 8 |
Correct |
23 ms |
50004 KB |
Output is correct |
| 9 |
Correct |
24 ms |
50004 KB |
Output is correct |
| 10 |
Correct |
22 ms |
49748 KB |
Output is correct |
| 11 |
Correct |
22 ms |
49876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
