| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 891811 | Trisanu_Das | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
int bit[2505];
int a[2][2505][2505], lst[2][2505][2505], cnt[2][2505][2505];
vector<pair<int, int> > p[2];
vector<int> s[2][2505];
void upd(int idx, int val){
for(idx++; idx < 2505; idx += (idx & -idx)) bit[idx] += val;
}
int qry(int idx){
int ans = 0;
for(idx++; idx; idx -= (idx & -idx)) ans += bit[idx];
return ans;
}
long long count_rectangles(vector<vector<int>> A) {
n = A.size(), m = A[0].size();
for(int i = 0; i < n; i++) s[0][i].push_back(0);
for(int i = 0; i < m; i++) s[1][i].push_back(0);
long long ans = 0;
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < m - 1; j++){
a[0][i][j] = a[1][j][i] = A[i][j];
a[0][i][j + 1] = A[i][j + 1];
a[1][j][i + 1] = A[i + 1][j];
for(int t = 0; t < 2; t++){
bool eq = 0;
p[t].clear();
while(!s[t][i].empty()){
int c = s[t][i].back();
if(c < j && !eq){
if(lst[t][c][j + 1] != i - 1) cnt[t][c][j + 1] = 0;
cnt[t][c][j + 1]++, lst[t][c][j + 1] = i;
p[t].push_back({j - c, cnt[t][c][j + 1]});
if(t) swap(p[t].back().first, p[t].back().second);
}
eq = a[t][i][c] == a[t][i][j + 1];
if(a[t][i][c] <= a[t][i][j + 1]) s[t][i].pop_back();
else break;
}
s[t][i].push_back(j + 1);
swap(i, j);
sort(p[t].begin(), p[t].end(), greater<pair<int, int> >());
}
int it = 0;
for(pair<int, int> v : p[0]){
for(; it < p[1].size() && v.f <= p[1][it].first; it++) upd(p[1][it].second, 1);
ans += qry(v.second);
}
for(int jt = 0; jt < it; jt++) upd(p[1][jt].second, -1);
}
}
return ans;
}