leetcode

commit 50f0daddb5054bf4eb982e04f7fc88c4043093e1
parent e6ae45a905a90b80fffa4e2f833165f0060ff49a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  4 Aug 2024 12:22:34 +0200

1 Random Problem

Diffstat:
A
Problems/2013.cpp
 | 
34
++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 35 insertions(+), 0 deletions(-)
diff --git a/Problems/2013.cpp b/Problems/2013.cpp
@@ -0,0 +1,34 @@
+class DetectSquares {
+    using point_t = tuple<int, int>;
+
+    unordered_map<int, unordered_set<int>> ys;
+    static int cnt[1001][1001];
+
+  public:
+    DetectSquares() { memset(cnt, 0x00, sizeof(cnt)); }
+
+    void add(const vector<int> &point) {
+        const int x = point[0];
+        const int y = point[1];
+
+        cnt[x][y]++;
+        ys[x].insert(y);
+    }
+
+    int count(const vector<int> &point) {
+        const int x = point[0];
+        const int y = point[1];
+        int res = 0;
+
+        for (const auto yp : ys[point[0]]) {
+            const int len = abs(y - yp);
+            if (!len) continue;
+            if (x + len <= 1000) res += cnt[x][yp] * cnt[x + len][y] * cnt[x + len][yp];
+            if (x >= len) res += cnt[x][yp] * cnt[x - len][y] * cnt[x - len][yp];
+        }
+
+        return res;
+    }
+};
+
+int DetectSquares::cnt[1001][1001];
diff --git a/README.md b/README.md
@@ -1047,6 +1047,7 @@ for solving problems.
 |  2001  |   Medium   | [Number of Pairs of Interchangeable Rectangles](Problems/2001.cpp)                                 |
 |  2002  |   Medium   | [Maximum Product of the Length of Two Palindromic Subsequences](Problems/2002.cpp)                 |
 |  2009  |    Hard    | [Minimum Number of Operations to Make Array Continuous](Problems/2009.cpp)                         |
+|  2013  |   Medium   | [Detect Squares](Problems/2013.cpp)                                                                |
 |  2023  |   Medium   | [Number of Pairs of Strings With Concatenation Equal to Target](Problems/2023.cpp)                 |
 |  2024  |   Medium   | [Maximize the Confusion of an Exam](Problems/2024.cpp)                                             |
 |  2033  |   Medium   | [Minimum Operations to Make a Uni-Value Grid](Problems/2033.cpp)                                   |