fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = (int)1e18 + 462010;
  17. const int MAX_N = 1e5;
  18.  
  19. int n, m, k, W;
  20. vector<int> cnt, s1, s2, u;
  21. vector<array<int, 4>> rec;
  22.  
  23. int id(int i, int j){
  24.     return i * W + j;
  25. }
  26.  
  27. void upd(int r, int c, int sg, int x){
  28.     int p = id(r, c);
  29.     cnt[p] += sg;
  30.     s1[p] += sg * x;
  31.     s2[p] += sg * x * x;
  32. }
  33.  
  34. void Input(){
  35.     cin >> n >> m >> k;
  36.     rec.resize(k + 1);
  37.     FOR(i, 1, k){
  38.         cin >> rec[i][0] >> rec[i][1] >> rec[i][2] >> rec[i][3];
  39.     }
  40. }
  41.  
  42. void Prepare(){
  43.     W = m + 2;
  44.     int tot = (n + 2) * W;
  45.     cnt.assign(tot, 0);
  46.     s1.assign(tot, 0);
  47.     s2.assign(tot, 0);
  48.     u.assign(k + 1, 0);
  49.  
  50.     FOR(i, 1, k){
  51.         int r1 = rec[i][0], c1 = rec[i][1], r2 = rec[i][2], c2 = rec[i][3];
  52.         upd(r1, c1, 1, i);
  53.         upd(r1, c2 + 1, -1, i);
  54.         upd(r2 + 1, c1, -1, i);
  55.         upd(r2 + 1, c2 + 1, 1, i);
  56.     }
  57.  
  58.     FOR(i, 1, n) FOR(j, 1, m){
  59.         int p = id(i, j);
  60.         int a = id(i - 1, j), b = id(i, j - 1), c = id(i - 1, j - 1);
  61.         cnt[p] += cnt[a] + cnt[b] - cnt[c];
  62.         s1[p] += s1[a] + s1[b] - s1[c];
  63.         s2[p] += s2[a] + s2[b] - s2[c];
  64.     }
  65. }
  66.  
  67. void Solve(){
  68.     int T = 0;
  69.     vector<int> prs;
  70.  
  71.     FOR(i, 1, n) FOR(j, 1, m){
  72.         int p = id(i, j);
  73.         if(cnt[p] >= 1) T++;
  74.  
  75.         if(cnt[p] == 1){
  76.             u[s1[p]]++;
  77.         }
  78.         else if(cnt[p] == 2){
  79.             int s = s1[p], q = s2[p];
  80.             int d2 = 2 * q - s * s;
  81.             int d = (int)sqrtl((long double)d2);
  82.             while(d * d > d2) d--;
  83.             while((d + 1) * (d + 1) <= d2) d++;
  84.             int x = (s - d) / 2, y = (s + d) / 2;
  85.             prs.pb(x * (k + 1) + y);
  86.         }
  87.     }
  88.  
  89.     sort(all(prs));
  90.  
  91.     vector<int> keys, ws;
  92.     for(int i = 0; i < sz(prs); ){
  93.         int j = i;
  94.         while(j < sz(prs) && prs[j] == prs[i]) j++;
  95.         keys.pb(prs[i]);
  96.         ws.pb(j - i);
  97.         i = j;
  98.     }
  99.  
  100.     int best = INF;
  101.  
  102.     FOR(t, 0, sz(keys) - 1){
  103.         int x = keys[t] / (k + 1), y = keys[t] % (k + 1);
  104.         best = min(best, u[x] + u[y] + ws[t]);
  105.     }
  106.  
  107.     vector<int> ord(k);
  108.     iota(all(ord), 1);
  109.     sort(all(ord), [&](int a, int b){
  110.         return u[a] < u[b];
  111.     });
  112.  
  113.     FOR(a, 0, k - 1){
  114.         bool found = false;
  115.         FOR(b, a + 1, k - 1){
  116.             int x = min(ord[a], ord[b]), y = max(ord[a], ord[b]);
  117.             int code = x * (k + 1) + y;
  118.             if(!binary_search(all(keys), code)){
  119.                 best = min(best, u[x] + u[y]);
  120.                 found = true;
  121.                 break;
  122.             }
  123.         }
  124.         if(!found && a + 1 >= k) break;
  125.     }
  126.  
  127.     cout << T - best << el;
  128. }
  129.  
  130. signed main(){
  131.     ios_base::sync_with_stdio(0);
  132.     cin.tie(0);
  133.  
  134.     Input();
  135.     Prepare();
  136.     Solve();
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1000000000000462010
https://ideone.com/B1vxzO
language:
C++ (gcc 8.3)
created:
12 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!