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;
  20. vector<vector<int>> a, P;
  21. vector<int> cnt, st;
  22. int ver = 0;
  23.  
  24. void ins(int x){
  25.     if(st[x] != ver){
  26.         st[x] = ver;
  27.         cnt[x] = 0;
  28.     }
  29.     cnt[x]++;
  30. }
  31.  
  32. int get(int x){
  33.     return st[x] == ver ? cnt[x] : 0;
  34. }
  35.  
  36. void Input(){
  37.     cin >> n >> m >> K;
  38.     a.assign(n + 1, vector<int>(m + 1, 0));
  39.     FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
  40. }
  41.  
  42. void Prepare(){
  43.     if(n > m){
  44.         vector<vector<int>> b(m + 1, vector<int>(n + 1, 0));
  45.         FOR(i, 1, n) FOR(j, 1, m) b[j][i] = a[i][j];
  46.         swap(a, b);
  47.         swap(n, m);
  48.     }
  49.  
  50.     P.assign(n + 1, vector<int>(m + 1, 0));
  51.     FOR(i, 1, n) FOR(j, 1, m){
  52.         int val = a[i][j] == -1 ? 0 : a[i][j] % K;
  53.         int cur = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + val;
  54.         cur %= K;
  55.         if(cur < 0) cur += K;
  56.         P[i][j] = cur;
  57.     }
  58.  
  59.     cnt.assign(K + 5, 0);
  60.     st.assign(K + 5, 0);
  61. }
  62.  
  63. void Solve(){
  64.     int ans = 0;
  65.  
  66.     FOR(u, 1, n){
  67.         vector<char> badc(m + 1, 0);
  68.  
  69.         FOR(v, u, n){
  70.             FOR(j, 1, m) if(a[v][j] == -1) badc[j] = 1;
  71.  
  72.             ver++;
  73.             ins(0);
  74.  
  75.             FOR(j, 1, m){
  76.                 int s = P[v][j] - P[u - 1][j];
  77.                 if(s < 0) s += K;
  78.  
  79.                 if(badc[j]){
  80.                     ver++;
  81.                     ins(s);
  82.                 }
  83.                 else{
  84.                     ans += get(s);
  85.                     ins(s);
  86.                 }
  87.             }
  88.         }
  89.     }
  90.  
  91.     cout << ans << el;
  92. }
  93.  
  94. signed main(){
  95.     ios_base::sync_with_stdio(0);
  96.     cin.tie(0);
  97.  
  98.     Input();
  99.     Prepare();
  100.     Solve();
  101.  
  102.     return 0;
  103. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/UNe4aJ
language:
C++ (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!