이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int bit[2509][2509];
int bitsz;
void upd(int x, int y, int val){
for(int i1 = x+1; i1 > 0; i1 -= i1&(-i1))
for(int i2 = y+1; i2 <= bitsz; i2 += i2&(-i2))
bit[i1][i2] += val;
}
int get(int x, int y){
int ret = 0;
for(int i1 = x+1; i1 <= bitsz; i1 += i1&(-i1))
for(int i2 = y+1; i2 > 0; i2 -= i2&(-i2))
ret += bit[i1][i2];
return ret;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size(), m = a[0].size();
bitsz = max(n, m);
for(int i = 1; i <= bitsz; ++i)
for(int j = 1; j <= bitsz; ++j)
bit[i][j] = 0;
vector<vector<vector<int>>> pos(m, vector<vector<int>>(m));
for(int i = 0; i < n; ++i){
vector<int> cur;
for(int j = m-1; j >= 0; --j){
while(cur.size() && a[i][cur.back()] < a[i][j]){
pos[j][cur.back()].pb(i);
cur.pop_back();
}
if(cur.size())
pos[j][cur.back()].pb(i);
while(cur.size() && a[i][cur.back()] <= a[i][j])
cur.pop_back();
cur.pb(j);
}
}
vector<vector<pair<pii, int>>> maxval(m);
/*for(int i = 0; i < n; ++i)
for(auto u : pos[i]){
if(u.ss) continue;
int j;
for(j = i+1; j < n; ++j){
auto it = lower_bound(all(pos[j]), u);
if(it == pos[j].end() || *it != u)
break;
it->ss = 1;
}
--j;
if(u.ff.ss-u.ff.ff > 1)
maxval[u.ff.ff].pb({{i, j}, u.ff.ss});
//cout << u.ff << ' ' << u.ss << ' ' << i << ' ' << j << '\n';
}*/
for(int x = 0; x < m; ++x)
for(int y = x+2; y < m; ++y)
for(int i = 0; i < pos[x][y].size();){
int j;
for(j = i+1; j < pos[x][y].size(); ++j)
if(pos[x][y][j] != pos[x][y][j-1]+1)
break;
int l = pos[x][y][i];
int r = pos[x][y][j-1];
//cout << x << ' ' << y << ' ' << l << ' ' << r << '\n';
maxval[x].pb({{l, r}, y});
i = j;
}
pos = vector<vector<vector<int>>>(n, vector<vector<int>>(n));
for(int i = 0; i < m; ++i){
vector<int> cur;
for(int j = n-1; j >= 0; --j){
while(cur.size() && a[cur.back()][i] < a[j][i]){
pos[j][cur.back()].pb(i);
cur.pop_back();
}
if(cur.size())
pos[j][cur.back()].pb(i);
while(cur.size() && a[cur.back()][i] <= a[j][i])
cur.pop_back();
cur.pb(j);
}
}
vector<vector<pair<pii, int>>> fin(m);
/*for(int i = 0; i < m; ++i)
for(auto u : pos[i]){
if(u.ss) continue;
int j;
for(j = i+1; j < m; ++j){
auto it = lower_bound(all(pos[j]), u);
if(it == pos[j].end() || *it != u)
break;
it->ss = 1;
}
--j;
if(u.ff.ss-u.ff.ff > 1)
for(int k = i; k <= j; ++k)
fin[k].pb({{u.ff.ff, u.ff.ss}, j});
}*/
for(int x = 0; x < n; ++x)
for(int y = x+2; y < n; ++y)
for(int i = 0; i < pos[x][y].size();){
int j;
for(j = i+1; j < pos[x][y].size(); ++j)
if(pos[x][y][j] != pos[x][y][j-1]+1)
break;
int l = pos[x][y][i];
int r = pos[x][y][j-1];
for(int k = l; k <= r; ++k)
fin[k].pb({{x, y}, r});
i = j;
}
ll ans = 0;
for(int i = 1; i < m; ++i){
sort(all(fin[i]));
sort(all(maxval[i-1]));
int curidx = 0;
for(auto u : fin[i]){
while(curidx < (int)maxval[i-1].size() && maxval[i-1][curidx].ff.ff <= u.ff.ff+1){
upd(maxval[i-1][curidx].ff.ss, maxval[i-1][curidx].ss, 1);
++curidx;
}
int val = get(u.ff.ss-1, u.ss+1);
//cout << i << ' ' << u.ss << ' ' << u.ff.ff << ' ' << u.ff.ss << ' ' << val << '\n';
ans += val;
}
for(int j = 0; j < curidx; ++j)
upd(maxval[i-1][j].ff.ss, maxval[i-1][j].ss, -1);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < pos[x][y].size();){
| ~~^~~~~~~~~~~~~~~~~~
rect.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(j = i+1; j < pos[x][y].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~
rect.cpp:119:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0; i < pos[x][y].size();){
| ~~^~~~~~~~~~~~~~~~~~
rect.cpp:121:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(j = i+1; j < pos[x][y].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~
# | 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... |