#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 2e9;
struct Segment {
int x1;
int y1;
int x2;
int y2;
};
const int MAX_N = 1e2;
vector<Segment> V;
vector<Segment> O;
vector<Segment> newV;
vector<Segment> newO;
map<int, vector<pair<int, int>>> mp;
bool cmpV(const Segment &A, const Segment &B) {
return (A.y1 < B.y1) || (A.y1 == B.y1 && A.x1 < B.x1) || (A.y1 == B.y1 && A.x1 == B.x1 && A.x2 < B.x2);
}
bool cmpO(const Segment &A, const Segment &B) {
return (A.x1 < B.x1) || (A.x1 == B.x1 && A.y1 < B.y1) || (A.x1 == B.x1 && A.y1 == B.y1 && A.y2 < B.y2);
}
bool InterVertical(Segment A, Segment B) {
return A.y1 == B.y1 && A.x1 >= B.x1 && A.x1 <= B.x2;
}
Segment UniteVertical(Segment A, Segment B) {
return Segment {B.x1, A.y1, max(A.x2, B.x2), A.y1};
}
bool InterOrizontal(Segment A, Segment B) {
return A.x1 == B.x1 && A.y1 >= B.y1 && A.y1 <= B.y2;
}
Segment UniteOrizontal(Segment A, Segment B) {
return Segment {A.x1, B.y1, A.x1, max(A.y2, B.y2)};
}
int main() {
#ifdef ONPC
freopen("input.txt", "r", stdin);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
V.push_back({-INF, x, +INF, x});
}
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
O.push_back({x, -INF, x, +INF});
}
sort(V.begin(), V.end(), cmpV);
sort(O.begin(), O.end(), cmpO);
for (int i = 0; i < V.size(); i++) {
if (!newV.empty() && InterVertical(V[i], newV.back())) {
Segment tmp = newV.back();
newV.pop_back();
newV.push_back(UniteVertical(V[i], tmp));
} else {
newV.push_back(V[i]);
}
}
for (int i = 0; i < O.size(); i++) {
if (!newO.empty() && InterOrizontal(O[i], newO.back())) {
Segment tmp = newO.back();
newO.pop_back();
newO.push_back(UniteOrizontal(O[i], tmp));
} else {
newO.push_back(O[i]);
}
}
for (int i = 0; i < newV.size(); i++) {
mp[newV[i].y1].push_back({newV[i].x1, newV[i].x2});
}
int answer = 0;
for (int i = 0; i < newO.size(); i++) {
for (int j = i + 1; j < newO.size(); j++) {
if (newO[j].x1 > newO[i].x1) {
for (int k = 0; k < newV.size(); k++) {
if (newV[k].x1 <= newO[i].x1 && newV[k].x2 >= newO[j].x1 && newV[k].y1 >= newO[i].y1 && newV[k].y1 <= newO[i].y2 && newV[k].y1 >= newO[j].y1 && newV[k].y1 <= newO[j].y2) {
int lat = newO[j].x1 - newO[i].x1;
if (newV[k].y1 + lat <= newO[i].y2 && newV[k].y1 + lat <= newO[j].y2) {
if (mp.find(newV[k].y1 + lat) != mp.end()) {
for (auto it : mp[newV[k].y1 + lat]) {
if (it.first <= newO[i].x1 && it.second >= newO[j].x1) {
answer++;
}
}
}
}
}
}
}
}
}
cout << answer;
return 0;
}
Compilation message
countsquares.cpp: In function 'int main()':
countsquares.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < V.size(); i++) {
| ~~^~~~~~~~~~
countsquares.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < O.size(); i++) {
| ~~^~~~~~~~~~
countsquares.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < newV.size(); i++) {
| ~~^~~~~~~~~~~~~
countsquares.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < newO.size(); i++) {
| ~~^~~~~~~~~~~~~
countsquares.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j = i + 1; j < newO.size(); j++) {
| ~~^~~~~~~~~~~~~
countsquares.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int k = 0; k < newV.size(); k++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
2707 ms |
596 KB |
Output is correct |
| 7 |
Correct |
2679 ms |
560 KB |
Output is correct |
| 8 |
Correct |
2712 ms |
564 KB |
Output is correct |
| 9 |
Correct |
2493 ms |
564 KB |
Output is correct |
| 10 |
Correct |
3383 ms |
560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
2707 ms |
596 KB |
Output is correct |
| 7 |
Correct |
2679 ms |
560 KB |
Output is correct |
| 8 |
Correct |
2712 ms |
564 KB |
Output is correct |
| 9 |
Correct |
2493 ms |
564 KB |
Output is correct |
| 10 |
Correct |
3383 ms |
560 KB |
Output is correct |
| 11 |
Execution timed out |
4021 ms |
980 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
