From 07f1e4daea1308562c2b87a7e408bc5688684ba8 Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Sun, 21 Mar 2021 23:03:47 +0800
Subject: import(solutions): Add acwing 1238.

---
 works/solutions/acwing/1238.cpp | 56 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)
 create mode 100644 works/solutions/acwing/1238.cpp

(limited to 'works')

diff --git a/works/solutions/acwing/1238.cpp b/works/solutions/acwing/1238.cpp
new file mode 100644
index 0000000..2c9d899
--- /dev/null
+++ b/works/solutions/acwing/1238.cpp
@@ -0,0 +1,56 @@
+#include <iostream>
+#include <map>
+#include <set>
+
+const int M = 100010;
+
+int N, D, K;
+
+std::map<int, std::multiset<int>> vote_map;
+
+bool check(const std::multiset<int> &v) {
+  auto iter1 = v.cbegin();
+  auto iter2 = v.cbegin();
+
+  const auto end = v.cend();
+
+  int count = 1;
+
+  while (iter2 != end) {
+    while (*iter2 - *iter1 >= D) {
+      ++iter1;
+      count--;
+    }
+
+    if (count >= K)
+      return true;
+
+    ++iter2;
+    count++;
+  }
+
+  return false;
+}
+
+int main() {
+  std::ios_base::sync_with_stdio(false);
+  std::cin.tie(nullptr);
+
+  std::cin >> N >> D >> K;
+
+  for (int i = 1; i <= N; i++) {
+    int ts, id;
+    std::cin >> ts >> id;
+    vote_map[id].insert(ts);
+  }
+
+  int result;
+
+  for (const auto &vote : vote_map) {
+    if (check(vote.second)) {
+      std::cout << vote.first << "\n";
+    }
+  }
+
+  return 0;
+}
-- 
cgit v1.2.3