#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 700;
int v[1 + nmax][1 + nmax];
int n, m;
namespace Dsu{
std::vector<int> mult;
std::vector<int> sz;
std::vector<int> maxid;
std::vector<int> minid;
void initialize(int n){
mult.resize(1 + n);
sz.resize(1 + n);
maxid.resize(1 + n);
minid.resize(1 + n);
for(int i = 1;i <= n; i++){
minid[i] = maxid[i] = mult[i] = i;
sz[i] = 1;
}
}
int jump(int gala){
if(gala != mult[gala])
mult[gala] = jump(mult[gala]);
return mult[gala];
}
void unite(int gala, int galb){
gala = jump(gala);
galb = jump(galb);
if(gala == galb)
return ;
if(sz[galb] < sz[gala])
std::swap(gala, galb);
sz[galb] += sz[gala];
mult[gala] = galb;
maxid[galb] = MAX(maxid[gala], maxid[galb]);
minid[galb] = MIN(minid[gala], minid[galb]);
}
}
std::vector<int> orizontal[1 + nmax][1 + nmax];
std::vector<int> vertical[1 + nmax][1 + nmax];
std::map<std::tuple<int,int,int>, int> freq;
struct Update{
int type;
int x;
int y;
int time;
bool operator < (Update const &a) const{
if(time != a.time)
return time < a.time;
else
return type < a.type;
}
};
int scount[1 + nmax][1 + (int)sqrt(nmax)];
ll solvelevel(int level){
std::map<std::pair<int,int>, int> freq2;
std::vector<Update> updates;
//std::cout << "Solve: " << level << '\n';
for(int i = 1;i < m - 1; i++){
for(int h = 0; h < orizontal[level][i].size(); h++){
int lim = orizontal[level][i][h];
freq[std::make_tuple(level, i, lim)] = freq[std::make_tuple(level + 1, i, lim)] + 1;
updates.push_back({1, i, lim, -freq[std::make_tuple(level, i, lim)]});
//std::cout << ":";
}
}
for(int i = 1;i < m - 1; i++){
for(int h = 0; h < vertical[level][i].size(); h++){
int lim = vertical[level][i][h];
freq2[{i, lim}] = freq2[{i - 1, lim}] + 1;
}
}
for(int i = 1;i < m - 1; i++){
for(int h = 0; h < vertical[level][i].size(); h++){
int lim = vertical[level][i][h];
if(0 == freq2[{i + 1, lim}]){
updates.push_back({2, i - freq2[{i, lim}] + 1, i, -(lim - i + 1) });
}
}
}
std::vector<Update> onlyupdates;
int rad = sqrt(m);
ll result = 0;
for(int i = 1;i <= m; i++)
for(int j = i; j <= MIN(i + rad, m); j++)
scount[i][j - i] = 0;
// std::cout << vertical[1][1].size() << '\n';
for(int i = 0; i < updates.size(); i++){
Update curr = updates[i];
//std::cout << curr.type << " " << curr.x << " " << curr.y << '\n';
if(curr.type == 1){
onlyupdates.push_back(curr);
int x = curr.x, y = curr.y;
while(1 <= x){
scount[x][y - x]++;
x--;
}
} else {
if((curr.y - curr.x) <= rad){
for(int j = curr.x; j <= curr.y; j++)
result += scount[curr.x][j - curr.x];
} else {
for(int j = 0; j < onlyupdates.size(); j++){
if(curr.x <= onlyupdates[j].x && onlyupdates[j].y <= curr.y)
result++;
}
}
}
}
//std::cout << level << " " << result << '\n';
return result;
}
long long count_rectangles(std::vector<std::vector<int> > a){
n = a.size();
m = a[0].size();
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
v[i][j] = a[i][j];
for(int i = 1; i < n - 1; i++){
std::vector<std::pair<int,int>> temp;
for(int j = 1;j < m - 1; j++)
temp.push_back({v[i][j], j});
sort(temp.begin(), temp.end());
Dsu::initialize(m);
for(int j = 0; j < temp.size(); j++){
int pos = temp[j].second;
if(v[i][pos - 1] < v[i][pos])
Dsu::unite(pos - 1, pos);
if(v[i][pos + 1] < v[i][pos])
Dsu::unite(pos + 1, pos);
int x = Dsu::minid[Dsu::jump(pos)], y = Dsu::maxid[Dsu::jump(pos)];
if(v[i][x - 1] > v[i][pos] && v[i][pos] < v[i][y + 1])
orizontal[i][x].push_back(y);
}
}
for(int i = 1; i < m - 1; i++){
std::vector<std::pair<int,int>> temp;
for(int j = 1;j < n - 1; j++)
temp.push_back({v[j][i], j});
sort(temp.begin(), temp.end());
Dsu::initialize(n);
for(int j = 0; j < temp.size(); j++){
int pos = temp[j].second;
if(v[pos - 1][i] < v[pos][i])
Dsu::unite(pos - 1, pos);
if(v[pos + 1][i] < v[pos][i])
Dsu::unite(pos + 1, pos);
int x = Dsu::minid[Dsu::jump(pos)], y = Dsu::maxid[Dsu::jump(pos)];
//std::cout << i << " " << x << " " << y << '\n';
if(v[x - 1][i] > v[pos][i] && v[pos][i] < v[y + 1][i])
vertical[x][i].push_back(y);
}
}
ll result = 0;
for(int i = n - 2; 1 <= i; i--)
result += solvelevel(i);
return result;
}
Compilation message
rect.cpp: In function 'll solvelevel(int)':
rect.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < orizontal[level][i].size(); h++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < vertical[level][i].size(); h++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < vertical[level][i].size(); h++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < updates.size(); i++){
~~^~~~~~~~~~~~~~~~
rect.cpp:128:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < onlyupdates.size(); j++){
~~^~~~~~~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:152:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < temp.size(); j++){
~~^~~~~~~~~~~~~
rect.cpp:170:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < temp.size(); j++){
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23416 KB |
Output is correct |
2 |
Correct |
23 ms |
23592 KB |
Output is correct |
3 |
Correct |
23 ms |
23672 KB |
Output is correct |
4 |
Correct |
23 ms |
23544 KB |
Output is correct |
5 |
Correct |
23 ms |
23544 KB |
Output is correct |
6 |
Incorrect |
24 ms |
23672 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23416 KB |
Output is correct |
2 |
Correct |
23 ms |
23592 KB |
Output is correct |
3 |
Correct |
23 ms |
23672 KB |
Output is correct |
4 |
Correct |
23 ms |
23544 KB |
Output is correct |
5 |
Correct |
23 ms |
23544 KB |
Output is correct |
6 |
Incorrect |
24 ms |
23672 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23416 KB |
Output is correct |
2 |
Correct |
23 ms |
23592 KB |
Output is correct |
3 |
Correct |
23 ms |
23672 KB |
Output is correct |
4 |
Correct |
23 ms |
23544 KB |
Output is correct |
5 |
Correct |
23 ms |
23544 KB |
Output is correct |
6 |
Incorrect |
24 ms |
23672 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23416 KB |
Output is correct |
2 |
Correct |
23 ms |
23592 KB |
Output is correct |
3 |
Correct |
23 ms |
23672 KB |
Output is correct |
4 |
Correct |
23 ms |
23544 KB |
Output is correct |
5 |
Correct |
23 ms |
23544 KB |
Output is correct |
6 |
Incorrect |
24 ms |
23672 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
23932 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
23416 KB |
Output is correct |
2 |
Runtime error |
128 ms |
102316 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23416 KB |
Output is correct |
2 |
Correct |
23 ms |
23592 KB |
Output is correct |
3 |
Correct |
23 ms |
23672 KB |
Output is correct |
4 |
Correct |
23 ms |
23544 KB |
Output is correct |
5 |
Correct |
23 ms |
23544 KB |
Output is correct |
6 |
Incorrect |
24 ms |
23672 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |