oj.uz

Submission #1036329

# Submission time Handle Problem Language Result Execution time Memory
1036329 2024-07-27T08:54:27 Z ind1v Count Squares (CEOI19_countsquares) C++11
100 / 100
 364 ms 9260 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1505;

int h, v;
int y[N], x[N];
vector<int> s;
int cnt[N * N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> h >> v;
  s.reserve(h * h);
  for (int i = 1; i <= h; i++) {
    cin >> y[i];
    for (int j = 1; j <= i - 1; j++) {
      s.emplace_back(y[i] - y[j]);
    }
  }
  sort(s.begin(), s.end());
  s.erase(unique(s.begin(), s.end()), s.end());
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= i - 1; j++) {
      cnt[lower_bound(s.begin(), s.end(), y[i] - y[j]) - s.begin()]++;
    }
  }
  long long ans = 0;
  for (int i = 1; i <= v; i++) {
    cin >> x[i];
    for (int j = 1; j <= i - 1; j++) {
      if (binary_search(s.begin(), s.end(), x[i] - x[j])) {
        ans += cnt[lower_bound(s.begin(), s.end(), x[i] - x[j]) - s.begin()];
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 48 ms 1880 KB Output is correct
7 Correct 52 ms 1716 KB Output is correct
8 Correct 44 ms 1884 KB Output is correct
9 Correct 50 ms 1624 KB Output is correct
10 Correct 13 ms 1112 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 48 ms 1880 KB Output is correct
7 Correct 52 ms 1716 KB Output is correct
8 Correct 44 ms 1884 KB Output is correct
9 Correct 50 ms 1624 KB Output is correct
10 Correct 13 ms 1112 KB Output is correct
11 Correct 343 ms 9044 KB Output is correct
12 Correct 364 ms 9260 KB Output is correct
13 Correct 343 ms 9244 KB Output is correct
14 Correct 343 ms 9044 KB Output is correct
15 Correct 108 ms 4904 KB Output is correct