fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug cerr << "No errors!"; exit(0);
  37. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b) for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define BIT(x, i) (((x) >> (i)) & 1)
  46. #define MASK(x) ((1LL) << (x))
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. #define mapa make_pair
  50. using namespace std;
  51. const int MOD = 1e9 + 7; // 998244353
  52. const int inf = 1e9;
  53. const ll INF = 1e18; // MASK(63) - 1
  54. const int N = 250;
  55.  
  56. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  57. ll random(const ll &L, const ll &R) {
  58.     return uniform_int_distribution<ll> (L, R) (rng);
  59. }
  60.  
  61. class SegmentTree {
  62. private:
  63.     int n;
  64.     vector <int> v;
  65.     void update(int id, int l, int r, int pos, int val) {
  66.         if (l > pos || pos > r) return;
  67.         if (l == r) {
  68.             v[id] = min(v[id], val);
  69.             return;
  70.         }
  71.         int mid = (l + r) >> 1;
  72.         update(id << 1, l, mid, pos, val);
  73.         update(id << 1 | 1, mid + 1, r, pos, val);
  74.         v[id] = min(v[id << 1], v[id << 1 | 1]);
  75.     }
  76.  
  77.     int get(int id, int l, int r, int fin) {
  78.         if (l > fin) return inf;
  79.         if (r <= fin) return v[id];
  80.         int mid = (l + r) >> 1;
  81.         return min(get(id << 1, l, mid, fin), get(id << 1 | 1, mid + 1, r, fin));
  82.     }
  83. public:
  84.     SegmentTree (int _n) {
  85.         n = _n;
  86.         v.resize(n * 4 + 1, inf);
  87.     }
  88.  
  89.     void update(int pos, int val) {
  90.         update(1, 1, n, pos, val);
  91.     }
  92.  
  93.     int get(int fin) {
  94.         return get(1, 1, n, fin);
  95.     }
  96. };
  97.  
  98. struct Rect {
  99.     int x1, y1, x2, y2, P;
  100.  
  101.     bool operator < (const Rect& other) const {
  102.         return P < other.P;
  103.     }
  104. };
  105.  
  106. vector <Rect> v;
  107.  
  108. int L, W, a[N + 5][N + 5], n, k, sum[N + 5][N + 5];
  109.  
  110. int get(int x, int y, int u, int v) {
  111.     return sum[u][v] - sum[x - 1][v] - sum[u][y - 1] + sum[x - 1][y - 1];
  112. }
  113.  
  114. int cook() {
  115.     int ans = inf;
  116.     int m = sz(v);
  117.     SegmentTree treex(L + 1);
  118.     forw (i, 0, m - 1) {
  119.         treex.update(v[i].x2, v[i].P);
  120.     }
  121.     forw (i, 0, m - 1) {
  122.         ans = min(ans, v[i].P + treex.get(v[i].x1 - 1));
  123.     }
  124.  
  125.     SegmentTree treey(W + 1);
  126.     forw (i, 0, m - 1) {
  127.         treey.update(v[i].y2, v[i].P);
  128.     }
  129.     forw (i, 0, m - 1) {
  130.         ans = min(ans, v[i].P + treey.get(v[i].y1 - 1));
  131.     }
  132.     return ans;
  133. }
  134.  
  135. void solve() {
  136.     cin >> L >> W >> n >> k;
  137.  
  138.     forw (i, 1, n) {
  139.         int x, y;
  140.         cin >> x >> y;
  141.         ++a[x][y];
  142.     }
  143.  
  144.     forw (i, 1, L) forw (j, 1, W)
  145.         sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
  146.  
  147.     forw (x1, 1, L) forw (x2, x1, L) {
  148.         int l = 1;
  149.         forw (r, 1, W) {
  150.             while (l <= r && get(x1, l, x2, r) > k) ++l;
  151.             if (l <= r && get(x1, l, x2, r) == k) {
  152.                 int y1 = l, y2 = r;
  153.                 int P = 2 * (x2 - x1 + 1 + y2 - y1 + 1);
  154.                 v.push_back({x1, y1, x2, y2, P});
  155.             }
  156.         }
  157.     }
  158.  
  159.     int res = cook();
  160.     if (res >= inf) {
  161.         cout << "NO\n";
  162.     }
  163.     else cout << res << endl;
  164. }
  165.  
  166.  
  167. signed main() {
  168.     ios::sync_with_stdio(false), cin.tie(nullptr);
  169.     srand(time(NULL));
  170.     #define name "test"
  171.     /*
  172.     if (fopen(name".INP", "r")) {
  173.         freopen(name".INP", "r", stdin);
  174.         freopen(name".OUT", "w", stdout);
  175.     }
  176.     */
  177.     bool testCase = false;
  178.     int numTest = 1;
  179.     // cin >> numTest;
  180.     forw (i, 1, numTest) {
  181.         if (testCase) cout << "Case " << i << ": ";
  182.         solve();
  183.     }
  184.     return 0;
  185. }
  186.  
  187. /*
  188.   /\__/\
  189.  (=^.^= )
  190.  (") (")_/
  191. */
  192.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/qZ8ne1
language:
C++14 (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!