daily pastebin goal
4%
SHARE
TWEET

Untitled

a guest Oct 18th, 2018 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long I64;
  6.  
  7. I64 sp[1010][1010];
  8. I64 fr[10000010];
  9.  
  10. int main()
  11. {
  12.     ios_base::sync_with_stdio(0);
  13.     cin.tie(0);
  14.     cout.tie(0);
  15.  
  16.     int N, K, Q;
  17.     cin >> N >> K >> Q;
  18.  
  19.     assert(K <= N * N);
  20.     assert(N <= 200);
  21.  
  22.     set <pair <int, int>> s;
  23.  
  24.     while (K--) {
  25.         int x, y;
  26.         cin >> x >> y;
  27.         assert(s.find({ x, y }) == s.end());
  28.         s.insert({ x , y });
  29.         sp[x][y]++;
  30.     }
  31.  
  32.     for (int i = 1; i <= N; ++i)
  33.         for (int j = 1; j <= N; ++j)
  34.             sp[i][j] += sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];
  35.  
  36.     for (int a = 1; a <= N; ++a)
  37.         for (int b = 1; b <= N; ++b)
  38.             for (int c = a; c <= N; ++c)
  39.                 for (int d = b; d <= N; ++d)
  40.                     fr[sp[c][d] - sp[a - 1][d] - sp[c][b - 1] + sp[a - 1][b - 1]]++;
  41.  
  42.     for (int i = 1; i <= N * N; i++)
  43.         fr[i] += fr[i - 1];
  44.  
  45.     I64 ans = 0;
  46.     while (Q--) {
  47.         int z;
  48.         cin >> z;
  49.         if (z <= N * N)
  50.             ans += fr[z];
  51.     }
  52.  
  53.     cout << ans << '\n';
  54.  
  55.     return 0;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top