oj.uz

Submission #1069764

# Submission time Handle Problem Language Result Execution time Memory
1069764 2024-08-22T08:48:00 Z TAhmed33 Rectangles (IOI19_rect) C++17
100 / 100
 2612 ms 995456 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize ("Ofast")
const int B = 3000;
struct BIT {
  int tree[B];
  void add (int x, int y) {
    for (; x < B; x += x & (-x)) {
      tree[x] += y;
    }
  }
  int get (int x) {
    int sum = 0;
    for (; x > 0; x -= x & (-x)) {
      sum += tree[x];
    }
    return sum;
  }
 
} cur;
vector <int> ii[2501][2501], jj[2501][2501];
vector <pair <int, int>> gg[2501][2501], hh[2501][2501];
int last[2501][2501], dd[2501][2501];
ll count_rectangles (vector <vector <int>> a) {
  int n = a.size(), m = a[0].size();
  for (int i = 0; i < n; i++) {
    stack <int> cur;
    cur.push(0);
    for (int j = 1; j < m; j++) {
      while (!cur.empty() && a[i][j] > a[i][cur.top()]) {
        cur.pop();
      }
      if (!cur.empty() && cur.top() + 1 <= j - 1) {
        ii[i][j - 1].push_back(cur.top() + 1);
      }
      cur.push(j);
    }
    while (!cur.empty()) {
      cur.pop();
    }
    cur.push(m - 1);
    for (int j = m - 2; j >= 0; j--) {
      while (!cur.empty() && a[i][j] > a[i][cur.top()]) {
        cur.pop();
      }
      if (!cur.empty() && j + 1 <= cur.top() - 1 && a[i][j] != a[i][cur.top()]) {
        ii[i][cur.top() - 1].push_back(j + 1);
      }
      cur.push(j);
    }
  }
  for (int i = 0; i < m; i++) {
    stack <int> cur;
    cur.push(0);
    for (int j = 1; j < n; j++) {
      while (!cur.empty() && a[j][i] > a[cur.top()][i]) {
        cur.pop();
      }
      if (!cur.empty() && cur.top() + 1 <= j - 1) {
        jj[j - 1][i].push_back(cur.top() + 1);
      }
      cur.push(j);
    }
    while (!cur.empty()) {
      cur.pop();
    }
    cur.push(n - 1);
    for (int j = n - 2; j >= 0; j--) {
      while (!cur.empty() && a[j][i] > a[cur.top()][i]) {
        cur.pop();
      }
      if (!cur.empty() && j + 1 <= cur.top() - 1 && a[j][i] != a[cur.top()][i]) {
        jj[cur.top() - 1][i].push_back(j + 1);
      }
      cur.push(j);
    }
  }
  for (int i = 0; i < n; i++) {
  	for (int j = 0; j < m; j++) {
  		last[i][j] = dd[i][j] = 0;
  	}
  }
  for (int i = 1; i + 1 < n; i++) {
    for (int j = 1; j + 1 < m; j++) {
      for (auto k : ii[i][j]) {
        if (last[k][j] == i - 1) {
          dd[k][j]++;
        } else {
          dd[k][j] = 1;
        }
        gg[i][j].push_back({j - k + 1, dd[k][j]});
        last[k][j] = i;
      }
      ii[i][j].clear(); ii[i][j].shrink_to_fit();
    }
  }
  for (int i = 0; i < n; i++) {
  	for (int j = 0; j < m; j++) {
  		last[i][j] = dd[i][j] = 0;
  	}
  }
  for (int j = 1; j + 1 < m; j++) {
    for (int i = 1; i + 1 < n; i++) {
      for (auto k : jj[i][j]) {
        if (last[k][i] == j - 1) {
          dd[k][i]++;
        } else {
          dd[k][i] = 1;
        }
        hh[i][j].push_back({i - k + 1, dd[k][i]});
        last[k][i] = j;
      }
      jj[i][j].clear(); jj[i][j].shrink_to_fit();
    }
  }
  ll ans = 0;
  for (int i = 1; i + 1 < n; i++) {
    for (int j = 1; j + 1 < m; j++) {
      sort(gg[i][j].begin(), gg[i][j].end(), [&] (pair <int, int> x, pair <int, int> y) {
        return x.second < y.second;
      });
      sort(hh[i][j].begin(), hh[i][j].end());
      reverse(hh[i][j].begin(), hh[i][j].end());
      int ptr = 0;
      vector <int> d;
      for (auto a : gg[i][j]) {
        while (!hh[i][j].empty() && hh[i][j].back().first <= a.second) {
          cur.add(hh[i][j].back().second, 1);
          d.push_back(hh[i][j].back().second);
          hh[i][j].pop_back();
        }
        ans += cur.get(B - 1) - cur.get(a.first - 1);
      }
      for (auto j : d) {
        cur.add(j, -1);
      }
    }
  }
  return ans;
}

Compilation message

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:125:11: warning: unused variable 'ptr' [-Wunused-variable]
  125 |       int ptr = 0;
      |           ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 587976 KB Output is correct
2 Correct 156 ms 588052 KB Output is correct
3 Correct 157 ms 588112 KB Output is correct
4 Correct 158 ms 588116 KB Output is correct
5 Correct 161 ms 588116 KB Output is correct
6 Correct 161 ms 588184 KB Output is correct
7 Correct 157 ms 588116 KB Output is correct
8 Correct 159 ms 588116 KB Output is correct
9 Correct 156 ms 588256 KB Output is correct
10 Correct 173 ms 588148 KB Output is correct
11 Correct 154 ms 588116 KB Output is correct
12 Correct 167 ms 588232 KB Output is correct
13 Correct 155 ms 587856 KB Output is correct
14 Correct 155 ms 587860 KB Output is correct
15 Correct 157 ms 588048 KB Output is correct
16 Correct 158 ms 587856 KB Output is correct
17 Correct 173 ms 587856 KB Output is correct
18 Correct 168 ms 587788 KB Output is correct
19 Correct 161 ms 588108 KB Output is correct
20 Correct 157 ms 588116 KB Output is correct
21 Correct 155 ms 588008 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 587976 KB Output is correct
2 Correct 156 ms 588052 KB Output is correct
3 Correct 157 ms 588112 KB Output is correct
4 Correct 158 ms 588116 KB Output is correct
5 Correct 161 ms 588116 KB Output is correct
6 Correct 161 ms 588184 KB Output is correct
7 Correct 157 ms 588116 KB Output is correct
8 Correct 159 ms 588116 KB Output is correct
9 Correct 156 ms 588256 KB Output is correct
10 Correct 173 ms 588148 KB Output is correct
11 Correct 154 ms 588116 KB Output is correct
12 Correct 167 ms 588232 KB Output is correct
13 Correct 155 ms 587856 KB Output is correct
14 Correct 155 ms 587860 KB Output is correct
15 Correct 157 ms 588048 KB Output is correct
16 Correct 158 ms 587856 KB Output is correct
17 Correct 173 ms 587856 KB Output is correct
18 Correct 168 ms 587788 KB Output is correct
19 Correct 161 ms 588108 KB Output is correct
20 Correct 157 ms 588116 KB Output is correct
21 Correct 155 ms 588008 KB Output is correct
22 Correct 158 ms 588864 KB Output is correct
23 Correct 156 ms 588884 KB Output is correct
24 Correct 157 ms 588884 KB Output is correct
25 Correct 161 ms 588884 KB Output is correct
26 Correct 159 ms 588928 KB Output is correct
27 Correct 157 ms 588884 KB Output is correct
28 Correct 159 ms 588884 KB Output is correct
29 Correct 163 ms 588608 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 587976 KB Output is correct
2 Correct 156 ms 588052 KB Output is correct
3 Correct 157 ms 588112 KB Output is correct
4 Correct 158 ms 588116 KB Output is correct
5 Correct 161 ms 588116 KB Output is correct
6 Correct 161 ms 588184 KB Output is correct
7 Correct 157 ms 588116 KB Output is correct
8 Correct 159 ms 588116 KB Output is correct
9 Correct 156 ms 588256 KB Output is correct
10 Correct 173 ms 588148 KB Output is correct
11 Correct 154 ms 588116 KB Output is correct
12 Correct 167 ms 588232 KB Output is correct
13 Correct 155 ms 587856 KB Output is correct
14 Correct 155 ms 587860 KB Output is correct
15 Correct 157 ms 588048 KB Output is correct
16 Correct 158 ms 587856 KB Output is correct
17 Correct 158 ms 588864 KB Output is correct
18 Correct 156 ms 588884 KB Output is correct
19 Correct 157 ms 588884 KB Output is correct
20 Correct 161 ms 588884 KB Output is correct
21 Correct 159 ms 588928 KB Output is correct
22 Correct 157 ms 588884 KB Output is correct
23 Correct 159 ms 588884 KB Output is correct
24 Correct 163 ms 588608 KB Output is correct
25 Correct 173 ms 587856 KB Output is correct
26 Correct 168 ms 587788 KB Output is correct
27 Correct 161 ms 588108 KB Output is correct
28 Correct 157 ms 588116 KB Output is correct
29 Correct 155 ms 588008 KB Output is correct
30 Correct 163 ms 591188 KB Output is correct
31 Correct 188 ms 591080 KB Output is correct
32 Correct 171 ms 591184 KB Output is correct
33 Correct 175 ms 590924 KB Output is correct
34 Correct 182 ms 591956 KB Output is correct
35 Correct 188 ms 591956 KB Output is correct
36 Correct 184 ms 591980 KB Output is correct
37 Correct 179 ms 591956 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 587976 KB Output is correct
2 Correct 156 ms 588052 KB Output is correct
3 Correct 157 ms 588112 KB Output is correct
4 Correct 158 ms 588116 KB Output is correct
5 Correct 161 ms 588116 KB Output is correct
6 Correct 161 ms 588184 KB Output is correct
7 Correct 157 ms 588116 KB Output is correct
8 Correct 159 ms 588116 KB Output is correct
9 Correct 156 ms 588256 KB Output is correct
10 Correct 173 ms 588148 KB Output is correct
11 Correct 154 ms 588116 KB Output is correct
12 Correct 167 ms 588232 KB Output is correct
13 Correct 155 ms 587856 KB Output is correct
14 Correct 155 ms 587860 KB Output is correct
15 Correct 157 ms 588048 KB Output is correct
16 Correct 158 ms 587856 KB Output is correct
17 Correct 158 ms 588864 KB Output is correct
18 Correct 156 ms 588884 KB Output is correct
19 Correct 157 ms 588884 KB Output is correct
20 Correct 161 ms 588884 KB Output is correct
21 Correct 159 ms 588928 KB Output is correct
22 Correct 157 ms 588884 KB Output is correct
23 Correct 159 ms 588884 KB Output is correct
24 Correct 163 ms 588608 KB Output is correct
25 Correct 163 ms 591188 KB Output is correct
26 Correct 188 ms 591080 KB Output is correct
27 Correct 171 ms 591184 KB Output is correct
28 Correct 175 ms 590924 KB Output is correct
29 Correct 182 ms 591956 KB Output is correct
30 Correct 188 ms 591956 KB Output is correct
31 Correct 184 ms 591980 KB Output is correct
32 Correct 179 ms 591956 KB Output is correct
33 Correct 173 ms 587856 KB Output is correct
34 Correct 168 ms 587788 KB Output is correct
35 Correct 161 ms 588108 KB Output is correct
36 Correct 157 ms 588116 KB Output is correct
37 Correct 155 ms 588008 KB Output is correct
38 Correct 210 ms 610040 KB Output is correct
39 Correct 221 ms 614744 KB Output is correct
40 Correct 224 ms 614736 KB Output is correct
41 Correct 230 ms 619604 KB Output is correct
42 Correct 220 ms 615572 KB Output is correct
43 Correct 221 ms 615836 KB Output is correct
44 Correct 237 ms 616120 KB Output is correct
45 Correct 217 ms 614996 KB Output is correct
46 Correct 223 ms 609872 KB Output is correct
47 Correct 245 ms 612432 KB Output is correct
48 Correct 319 ms 623212 KB Output is correct
49 Correct 332 ms 625492 KB Output is correct
50 Correct 240 ms 610640 KB Output is correct
51 Correct 253 ms 609620 KB Output is correct
52 Correct 312 ms 622672 KB Output is correct
53 Correct 328 ms 623696 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 608468 KB Output is correct
2 Correct 178 ms 605252 KB Output is correct
3 Correct 170 ms 588112 KB Output is correct
4 Correct 180 ms 587860 KB Output is correct
5 Correct 167 ms 598352 KB Output is correct
6 Correct 173 ms 598356 KB Output is correct
7 Correct 172 ms 598352 KB Output is correct
8 Correct 164 ms 597664 KB Output is correct
9 Correct 181 ms 597212 KB Output is correct
10 Correct 219 ms 587864 KB Output is correct
11 Correct 174 ms 588112 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 587856 KB Output is correct
2 Correct 168 ms 587788 KB Output is correct
3 Correct 161 ms 588108 KB Output is correct
4 Correct 157 ms 588116 KB Output is correct
5 Correct 155 ms 588008 KB Output is correct
6 Correct 198 ms 587852 KB Output is correct
7 Correct 778 ms 693828 KB Output is correct
8 Correct 1189 ms 795224 KB Output is correct
9 Correct 1142 ms 795776 KB Output is correct
10 Correct 1107 ms 795944 KB Output is correct
11 Correct 272 ms 642320 KB Output is correct
12 Correct 404 ms 694068 KB Output is correct
13 Correct 431 ms 697768 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 587976 KB Output is correct
2 Correct 156 ms 588052 KB Output is correct
3 Correct 157 ms 588112 KB Output is correct
4 Correct 158 ms 588116 KB Output is correct
5 Correct 161 ms 588116 KB Output is correct
6 Correct 161 ms 588184 KB Output is correct
7 Correct 157 ms 588116 KB Output is correct
8 Correct 159 ms 588116 KB Output is correct
9 Correct 156 ms 588256 KB Output is correct
10 Correct 173 ms 588148 KB Output is correct
11 Correct 154 ms 588116 KB Output is correct
12 Correct 167 ms 588232 KB Output is correct
13 Correct 155 ms 587856 KB Output is correct
14 Correct 155 ms 587860 KB Output is correct
15 Correct 157 ms 588048 KB Output is correct
16 Correct 158 ms 587856 KB Output is correct
17 Correct 158 ms 588864 KB Output is correct
18 Correct 156 ms 588884 KB Output is correct
19 Correct 157 ms 588884 KB Output is correct
20 Correct 161 ms 588884 KB Output is correct
21 Correct 159 ms 588928 KB Output is correct
22 Correct 157 ms 588884 KB Output is correct
23 Correct 159 ms 588884 KB Output is correct
24 Correct 163 ms 588608 KB Output is correct
25 Correct 163 ms 591188 KB Output is correct
26 Correct 188 ms 591080 KB Output is correct
27 Correct 171 ms 591184 KB Output is correct
28 Correct 175 ms 590924 KB Output is correct
29 Correct 182 ms 591956 KB Output is correct
30 Correct 188 ms 591956 KB Output is correct
31 Correct 184 ms 591980 KB Output is correct
32 Correct 179 ms 591956 KB Output is correct
33 Correct 210 ms 610040 KB Output is correct
34 Correct 221 ms 614744 KB Output is correct
35 Correct 224 ms 614736 KB Output is correct
36 Correct 230 ms 619604 KB Output is correct
37 Correct 220 ms 615572 KB Output is correct
38 Correct 221 ms 615836 KB Output is correct
39 Correct 237 ms 616120 KB Output is correct
40 Correct 217 ms 614996 KB Output is correct
41 Correct 223 ms 609872 KB Output is correct
42 Correct 245 ms 612432 KB Output is correct
43 Correct 319 ms 623212 KB Output is correct
44 Correct 332 ms 625492 KB Output is correct
45 Correct 240 ms 610640 KB Output is correct
46 Correct 253 ms 609620 KB Output is correct
47 Correct 312 ms 622672 KB Output is correct
48 Correct 328 ms 623696 KB Output is correct
49 Correct 189 ms 608468 KB Output is correct
50 Correct 178 ms 605252 KB Output is correct
51 Correct 170 ms 588112 KB Output is correct
52 Correct 180 ms 587860 KB Output is correct
53 Correct 167 ms 598352 KB Output is correct
54 Correct 173 ms 598356 KB Output is correct
55 Correct 172 ms 598352 KB Output is correct
56 Correct 164 ms 597664 KB Output is correct
57 Correct 181 ms 597212 KB Output is correct
58 Correct 219 ms 587864 KB Output is correct
59 Correct 174 ms 588112 KB Output is correct
60 Correct 198 ms 587852 KB Output is correct
61 Correct 778 ms 693828 KB Output is correct
62 Correct 1189 ms 795224 KB Output is correct
63 Correct 1142 ms 795776 KB Output is correct
64 Correct 1107 ms 795944 KB Output is correct
65 Correct 272 ms 642320 KB Output is correct
66 Correct 404 ms 694068 KB Output is correct
67 Correct 431 ms 697768 KB Output is correct
68 Correct 173 ms 587856 KB Output is correct
69 Correct 168 ms 587788 KB Output is correct
70 Correct 161 ms 588108 KB Output is correct
71 Correct 157 ms 588116 KB Output is correct
72 Correct 155 ms 588008 KB Output is correct
73 Correct 758 ms 799000 KB Output is correct
74 Correct 855 ms 862932 KB Output is correct
75 Correct 1140 ms 862804 KB Output is correct
76 Correct 1093 ms 928128 KB Output is correct
77 Correct 1020 ms 868204 KB Output is correct
78 Correct 1496 ms 826708 KB Output is correct
79 Correct 1683 ms 854896 KB Output is correct
80 Correct 2612 ms 968072 KB Output is correct
81 Correct 1592 ms 843512 KB Output is correct
82 Correct 2050 ms 923476 KB Output is correct
83 Correct 2583 ms 995456 KB Output is correct
84 Correct 1504 ms 821504 KB Output is correct
85 Correct 2567 ms 977336 KB Output is correct
86 Correct 2282 ms 966012 KB Output is correct
87 Correct 695 ms 776056 KB Output is correct
88 Correct 1027 ms 868220 KB Output is correct
89 Correct 1029 ms 868136 KB Output is correct
90 Correct 1073 ms 868272 KB Output is correct