CP_Codes/B_Count_Subrectangles.cpp at main · nishantlamba29/CP_Codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
#define int long long

inline void n_lamba_29() {

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n), b(m);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<m;i++) cin >> b[i];

    vector<int> t1(n+1, 0), t2(m+1, 0);

    int lo = 0;
    while (lo < n) {
        int cnt = 0;
        while (lo < n && a[lo] == 1) {
            lo++;
            cnt++;
        }
        lo++;
        int val = 1;
        for (int j = cnt; j >= 1; j--) {
            t1[j] += val;
            val++;
        }
    }
    lo = 0;
    while (lo < m) {
        int cnt = 0;
        while (lo < m && b[lo] == 1) {
            lo++;
            cnt++;
        }
        lo++;
        int val = 1;
        for (int j = cnt; j >= 1; j--) {
            t2[j] += val;
            val++;
        }
    }

    vector<int> divisors;
    for(int i=1;i*i<=k;i++) {
        if(k % i == 0) {
            divisors.push_back(i);
            if(i*i != k) divisors.push_back(k / i);
        }
    }

    sort(divisors.begin(), divisors.end());

    int ans = 0;
    for(auto p : divisors) {
        int q = k / p;
        if(p <=n && q <= m)
        ans += (t1[p] *  t2[q]);
    }

    cout << ans << "\n";

}


int32_t main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int _ = 1;
    // cin >> _;
    while (_-->0) {
        n_lamba_29();
    }


    return 0;
}