fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(v) (v).begin(), (v).end()
  3. #define int long long
  4. #define rep(i, l, r) for (int i = l; i <= r; ++i)
  5. #define repd(i, r, l) for (int i = r; i >= l; --i)
  6. #define _unique(x) (x).resize(unique((x).begin(), (x).end()) - (x).begin());
  7. #define sz(v) (int)(v).size()
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define pf push_front
  12. #define mp make_pair
  13. #define eps double(1e-9)
  14. #define vii vector<int>
  15. #define pii pair<int,int>
  16. #define p2i pair<int,pii>
  17. #define endl '\n'
  18.  
  19. using namespace std;
  20.  
  21. const int N = 1e6 + 5;
  22. const int MN = 2e3 + 5;
  23. // const int mod = 1e9 + 7;
  24. const int inf = 1e18 + 7;
  25. const bool Emily = false;
  26.  
  27. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  28. int rnd(int l, int r) {
  29.     return l+rng()%(r-l+1);
  30. }
  31.  
  32. bool minimize(int &a, int b) {
  33.     if (a > b) {
  34.         a = b;
  35.         return 1;
  36.     }
  37.     return 0;
  38. }
  39.  
  40. bool maximize(int &a, int b) {
  41.     if (a < b) {
  42.         a = b;
  43.         return 1;
  44.     }
  45.     return 0;
  46. }
  47.  
  48. struct emily {
  49.     int x, y, u, v;
  50.  
  51.     emily(int _x, int _y, int _u, int _v) {
  52.         x = _x, y = _y, u = _u, v = _v;
  53.     }
  54.  
  55.     bool operator < (const emily &other) const{
  56.         return (x == other.x && y == other.y && u >= other.u && v >= other.v);
  57.     }
  58. };
  59.  
  60. int n, m, k;
  61. vector <vii> a;
  62. vector <vii> f;
  63. vector <vector <pii> > qu;
  64. vector <emily> queries;
  65.  
  66. void mod(int &x) {
  67.     x %= 3;
  68.     if (x < 0) x += 3;
  69. }
  70.  
  71. int cal(int x) {
  72.     f = vector <vii > (n + 2, vii (m + 2, 0));
  73.     int res = 0;
  74.  
  75.     for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
  76.         f[i][j] = f[i][j] + f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
  77.         mod(f[i][j]);
  78.  
  79.         int cur = a[i][j] + f[i][j];
  80.         mod(cur);
  81.  
  82.         if (cur == x) continue ;
  83.  
  84.         //auto p = *(lower_bound(ALL(queries), emily(i, j, 0, 0)));
  85.         //int u = p.u; int v = p.v;
  86.  
  87.         int u = qu[i][j].fi, v = qu[i][j].se;
  88.  
  89.         if (u == 0) return inf;
  90.         int cnt = (x - cur + 3) % 3;
  91.  
  92.         res += cnt;
  93.         // (i, j) (u, v)
  94.  
  95.         f[i][j] += cnt; f[i][v + 1] -= cnt;
  96.         f[u + 1][j] -= cnt; f[u + 1][v + 1] += cnt;
  97.     }
  98.  
  99.     return res;
  100. }
  101.  
  102. void solve(void) {
  103.     cin >> n >> m >> k;
  104.  
  105.     a = vector <vii > (n + 2, vii (m + 2, 0));
  106.     qu = vector <vector <pii > > (n + 2, vector <pii> (m + 2, {0, 0}));
  107.  
  108.     for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j];
  109.  
  110.     for (int i = 1; i <= k; ++i) {
  111.         int x, y, u, v;
  112.         cin >> x >> y >> u >> v;
  113.         //queries.pb(emily(x, y, u, v));
  114.         qu[x][y] = mp(u, v);
  115.     }
  116.  
  117.     int res = min(cal(1), cal(2));
  118.  
  119.     if (res == inf) cout << -1 << endl ;
  120.     else cout << res << endl;
  121. }
  122.  
  123. signed main()
  124. {
  125.     #define task "LIGHT"
  126.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  127.  
  128.     // freopen(task".inp", "r", stdin);
  129.     // freopen(task".out", "w", stdout);
  130.  
  131.     if (Emily) {
  132.         int t; cin >> t;
  133.         while (t-- ) solve();
  134.     } else solve();
  135.  
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/lHCRBi
language:
C++ (gcc 8.3)
created:
2 years 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!