| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 473321 | blue | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
include "rect.h"
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <iostream>
using namespace std;
/*
Red = | |
| |
Green = ----
----
*/
vector<int> green_R2;
vector<int> green_C2;
vector<int> red_R2;
vector<int> red_C2;
int R, G;
long long count_rectangles(vector< vector<int> > A)
{
int N = (int)A.size();
int M = (int)A[0].size();
vector< vector< vector<int> > > red_occ(M, vector< vector<int> >(M));
for(int i = 0; i < N; i++)
{
vector<int> st;
st.push_back(-1);
for(int j = 0; j < M; j++)
{
// if(i == 1)
// {
// // cerr << "j = " << j << '\n';
// // cerr << "st = ";
// // for(int h: st) cerr << h << ' ';
// // cerr << '\n';
// }
while(st.back() != -1 && A[i][st.back()] < A[i][j])
{
if(st.back() != j-1)
{
// if(i == 1) cerr << "red " << st.back() + 1 << ' ' << j-1 << '\n';
red_occ[ st.back() + 1 ][j - 1].push_back(i);
}
st.pop_back();
}
if(st.back() != j-1 && st.back() != -1)
{
// if(i == 1) cerr << "red " << st.back() + 1 << ' ' << j-1 << '\n';
red_occ[ st.back() + 1 ][j - 1].push_back(i);
}
while(st.back() != -1 && A[i][st.back()] == A[i][j])
st.pop_back();
st.push_back(j);
}
}
// cerr << "Red\n";
vector<int> red_r1, red_r2, red_c1, red_c2;
for(int c1 = 0; c1 < M; c1++)
{
for(int c2 = c1; c2 < M; c2++)
{
if(red_occ[c1][c2].empty()) continue;
vector<int> B, E;
B.push_back(red_occ[c1][c2][0]);
for(int x = 0; x+1 < (int)red_occ[c1][c2].size(); x++)
{
if(red_occ[c1][c2][x] + 1 != red_occ[c1][c2][x+1])
{
E.push_back(red_occ[c1][c2][x]);
B.push_back(red_occ[c1][c2][x+1]);
}
}
E.push_back(red_occ[c1][c2].back());
for(int q = 0; q < (int)B.size(); q++)
{
// cerr << B[q] << ' ' << c1 << ' ' << E[q] << ' ' << c2 << '\n';
red_r1.push_back(B[q]);
red_r2.push_back(E[q]);
red_c1.push_back(c1);
red_c2.push_back(c2);
}
}
}
red_occ.clear();
vector<int> red_opp_r[N][M], red_opp_c[N][M];
for(int q = 0; q < (int)red_r1.size(); q++)
{
for(int r = red_r1[q]; r <= red_r2[q]; r++)
{
red_opp_r[r][red_c1[q]].push_back(red_r2[q]);
red_opp_c[r][red_c1[q]].push_back(red_c2[q]);
}
}
red_r1.clear();
red_r2.clear();
red_c1.clear();
red_c2.clear();
vector< vector< vector<int> > > green_occ(N, vector< vector<int> >(N)); //CHECK THAT EVERYTHING IS SYMMETRIC!!!!!
for(int j = 0; j < M; j++)
{
// cerr << "col = " << j << '\n';
vector<int> st;
st.push_back(-1);
for(int i = 0; i < N; i++)
{
while(st.back() != -1 && A[st.back()][j] < A[i][j])
{
if(st.back() != i-1)
{
// cerr << st.back() + 1 << ' ' << i-1 << '\n';
green_occ[st.back() + 1][i - 1].push_back(j);
}
st.pop_back();
}
if(st.back() != i-1 && st.back() != -1)
{
// cerr << st.back() + 1 << ' ' << i-1 << '\n';
green_occ[st.back() + 1][i - 1].push_back(j);
}
while(st.back() != -1 && A[st.back()][j] == A[i][j])
st.pop_back();
st.push_back(i);
}
}
// cerr << "check\n";
// cerr << "Green\n";
vector<int> green_r1, green_r2, green_c1, green_c2;
for(int r1 = 0; r1 < N; r1++)
{
for(int r2 = r1; r2 < N; r2++)
{
if(green_occ[r1][r2].empty()) continue;
// cer
vector<int> B, E;
B.push_back(green_occ[r1][r2][0]);
for(int x = 0; x+1 < (int)green_occ[r1][r2].size(); x++)
{
if(green_occ[r1][r2][x] + 1 != green_occ[r1][r2][x+1])
{
E.push_back(green_occ[r1][r2][x]);
B.push_back(green_occ[r1][r2][x+1]);
}
}
E.push_back(green_occ[r1][r2].back());
for(int q = 0; q < (int)B.size(); q++)
{
green_r1.push_back(r1);
green_r2.push_back(r2);
green_c1.push_back(B[q]);
green_c2.push_back(E[q]);
// cerr << r1 << ' ' << B[q] << ' ' << r2 << ' ' << E[q] << '\n';
}
}
}
green_occ.clear();
vector<int> green_opp_r[N][M], green_opp_c[N][M];
for(int q = 0; q < (int)green_r1.size(); q++)
{
for(int c = green_c1[q]; c <= green_c2[q]; c++)
{
green_opp_r[green_r1[q]][c].push_back(green_r2[q]);
green_opp_c[green_r1[q]][c].push_back(green_c2[q]);
}
}
green_r1.clear();
green_r2.clear();
green_c1.clear();
green_c2.clear();
for(int i = 0; i < N; i++)
A[i].clear();
A.clear();
int MX = 4'096;
vector<int> BIT(1+MX, 0);
long long res = 0;
for(int r1 = 0; r1 < N; r1++)
{
for(int c1 = 0; c1 < M; c1++)
{
long long res1 = res;
green_R2 = green_opp_r[r1][c1];
green_C2 = green_opp_c[r1][c1];
red_R2 = red_opp_r[r1][c1];
red_C2 = red_opp_c[r1][c1];
vector<int> I((int)green_R2.size() + (int)red_R2.size());
for(int i = 0; i < (int)I.size(); i++)
I[i] = i;
G = (int)green_R2.size();
R = (int)red_R2.size();
//sweep line by row
//fenwick tree by column
//green comes first
sort(I.begin(), I.end(), [] (int p, int q)
{
int r_p, c_p, r_q, c_q;
if(p < G)
{
r_p = green_R2[p];
c_p = green_C2[p];
}
else
{
r_p = red_R2[p - G];
c_p = red_C2[p - G];
}
if(q < G)
{
r_q = green_R2[q];
c_q = green_C2[q];
}
else
{
r_q = red_R2[q - G];
c_q = red_C2[q - G];
}
if(r_p != r_q) return r_p < r_q;
else return p < q;
});
for(int i:I)
{
if(i < G)
for(int b = green_C2[i]+1; b <= MX; b += b&-b)
BIT[b]++;
else
{
for(int b = MX; b >= 1; b -= b&-b)
res += BIT[b];
for(int b = red_C2[i - G]+1 - 1; b >= 1; b -= b&-b)
res -= BIT[b];
}
}
for(int i:I)
{
if(i < G)
for(int b = green_C2[i]+1; b <= MX; b += b&-b)
BIT[b] = 0;
}
// if(res != res1)
// {
// cout << "top left = " << r1 << ' ' << c1 << ", diff = " << res - res1 << '\n';
// }
}
}
return res;
}