| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 809218 | Username4132 | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
const int MAXN = 1510;
ull mask[MAXN][MAXN], moved[MAXN]; // column, start row
int n, m, arr[MAXN][MAXN], brr[MAXN][MAXN], maa[MAXN][MAXN];
int far[MAXN][MAXN][MAXN]; // row, l, r
void calc1(){
dforn(row, n){
forsn(i, 1, m-1){
int mx = -1;
forsn(j, i, m-1){
mx = max(mx, arr[row][j]);
if(mx<arr[row][i-1] && mx<arr[row][j+1]){
far[row][i][j]=far[row+1][i][j];
}
else far[row][i][j]=row;
}
}
}
}
void calc2(int x){
forn(i, n) forn(j, m) mask[i][j]=0;
forn(col, m){
forsn(i, 1, n-1){
forsn(j, i+(x<<6), min(n-1, i + ((x+1)<<6))){
maa[col][i] = max(maa[col][i], brr[col][j]);
if(maa[col][i]<brr[col][i-1] && maa[col][i]<brr[col][j+1]){
mask[i][col]|=(1ull<<(j-i-(x<<6)));
}
}
}
}
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n=(int)a.size(), m=(int)a.front().size();
//forn(i, 800) full|=(one<<i);
moved[0]=0;
forn(i, 64) moved[i+1]=(moved[i]<<1)|1;
forn(i, n) forn(j, m) brr[j][i]=arr[i][j]=a[i][j];
forn(i, m) forn(j, m) far[n][i][j]=n;
calc1();
ll ans=0;
forn(x, (n+63)>>6){
calc2(x);
forsn(row, 1, n-1){
forsn(i, 1, m-1){
ull bt = ~0ull;
forsn(j, i, m-1){
bt&=mask[row][j];
ans+=__builtin_popcountll((bt&moved[min(far[row][i][j]-row-(x<<6), 64)]));
}
}
}
}
return ans;
}