Submission #855551

#	Time	Username	Problem	Language	Result	Execution time	Memory
855551		tvladm2009	Count Squares (CEOI19_countsquares)	C++17	47 / 100	4021 ms	980 KiB

countsquares

#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 (stderr)

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++) {
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 40 / 40
• Subtask 3: 0 / 53