oj.uz

Submission #844766

# Submission time Handle Problem Language Result Execution time Memory
844766 2023-09-05T21:17:42 Z garyye Rectangles (IOI19_rect) C++17
100 / 100
 2839 ms 542324 KB 
#include "rect.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
typedef pair<int, int> i2;
typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;

const int N = 2505;
vector<int> C[N][N];
int L[N][N], R[N][N];
set<int> S[N];

long long count_rectangles(vvi A) {
  int n = SZ(A), m = SZ(A[0]);

  auto fun = [](vector<int> a) {
    vector<i2> ans;
    int s = SZ(a);
    vector<int> p(s), l(s, -1), r(s, -1);
    for (int i = 0; i < s; ++i) p[i] = i;
    sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });
    for (int i : p) {
      i2 x = {i, i};
      if (i > 0 && l[i - 1] != -1) x.fi = l[i - 1];
      if (i + 1 < s && r[i + 1] != -1) x.se = r[i + 1];

      if (x.fi > 0 && x.se + 1 < s && min(a[x.fi - 1], a[x.se + 1]) > a[i]) {
        ans.push_back(x);
      }
      r[x.fi] = x.se;
      l[x.se] = x.fi;
    }

    return ans;
  };

  for (int j = 0; j < m; ++j) {
    vector<int> col(n);
    for (int i = 0; i < n; ++i) col[i] = A[i][j];
    auto pp = fun(col);

    for (auto& [i1, i2] : pp) {
      C[i2][j].push_back(i1);
    }
  }

  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    vector<int> p(m), l(m, -1), r(m, -1);
    for (int j = 0; j < m; ++j) p[j] = j, S[j].clear();
    sort(p.begin(), p.end(), [&](int l, int r) -> bool { return A[i][l] < A[i][r]; });

    for (int j : p) {
      i2 x = {j, j};

      set<int> cur(ALL(C[i][j]));
      set<int> del;

      auto inspect = [&](set<int>& s) {
        for (int c : cur)
          if (!s.count(c))
            del.insert(c);
      };

      if (j > 0 && l[j - 1] != -1) {
        x.fi = l[j - 1];
        inspect(S[x.fi]);
      }
      if (j + 1 < m && r[j + 1] != -1) {
        x.se = r[j + 1];
        inspect(S[l[x.se]]);
      }

      for (int x : del) cur.erase(x);

      if (x.fi > 0 && x.se + 1 < m && min(A[i][x.fi - 1], A[i][x.se + 1]) > A[i][j]) {
        if (i - R[x.fi][x.se] > 1) {
          L[x.fi][x.se] = i;
        }
        R[x.fi][x.se] = i;
        for (int i1 : cur) {
          if (i1 >= L[x.fi][x.se]) {
            ans++;
          }
        }
      }
      r[x.fi] = x.se;
      l[x.se] = x.fi;
      S[x.fi] = cur;
    }
  }
  return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 149584 KB Output is correct
2 Correct 31 ms 149844 KB Output is correct
3 Correct 31 ms 149840 KB Output is correct
4 Correct 31 ms 149848 KB Output is correct
5 Correct 31 ms 149596 KB Output is correct
6 Correct 32 ms 149816 KB Output is correct
7 Correct 31 ms 149848 KB Output is correct
8 Correct 32 ms 149848 KB Output is correct
9 Correct 33 ms 149840 KB Output is correct
10 Correct 32 ms 149848 KB Output is correct
11 Correct 31 ms 149848 KB Output is correct
12 Correct 32 ms 149840 KB Output is correct
13 Correct 33 ms 149584 KB Output is correct
14 Correct 31 ms 149584 KB Output is correct
15 Correct 32 ms 149596 KB Output is correct
16 Correct 31 ms 149552 KB Output is correct
17 Correct 32 ms 149584 KB Output is correct
18 Correct 31 ms 149592 KB Output is correct
19 Correct 32 ms 153944 KB Output is correct
20 Correct 31 ms 149584 KB Output is correct
21 Correct 31 ms 149620 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 149584 KB Output is correct
2 Correct 31 ms 149844 KB Output is correct
3 Correct 31 ms 149840 KB Output is correct
4 Correct 31 ms 149848 KB Output is correct
5 Correct 31 ms 149596 KB Output is correct
6 Correct 32 ms 149816 KB Output is correct
7 Correct 31 ms 149848 KB Output is correct
8 Correct 32 ms 149848 KB Output is correct
9 Correct 33 ms 149840 KB Output is correct
10 Correct 32 ms 149848 KB Output is correct
11 Correct 31 ms 149848 KB Output is correct
12 Correct 32 ms 149840 KB Output is correct
13 Correct 33 ms 149584 KB Output is correct
14 Correct 31 ms 149584 KB Output is correct
15 Correct 32 ms 149596 KB Output is correct
16 Correct 31 ms 149552 KB Output is correct
17 Correct 32 ms 149584 KB Output is correct
18 Correct 31 ms 149592 KB Output is correct
19 Correct 32 ms 153944 KB Output is correct
20 Correct 31 ms 149584 KB Output is correct
21 Correct 31 ms 149620 KB Output is correct
22 Correct 33 ms 150436 KB Output is correct
23 Correct 34 ms 150352 KB Output is correct
24 Correct 32 ms 150360 KB Output is correct
25 Correct 33 ms 150360 KB Output is correct
26 Correct 34 ms 150352 KB Output is correct
27 Correct 34 ms 150364 KB Output is correct
28 Correct 36 ms 152656 KB Output is correct
29 Correct 32 ms 150096 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 149584 KB Output is correct
2 Correct 31 ms 149844 KB Output is correct
3 Correct 31 ms 149840 KB Output is correct
4 Correct 31 ms 149848 KB Output is correct
5 Correct 31 ms 149596 KB Output is correct
6 Correct 32 ms 149816 KB Output is correct
7 Correct 31 ms 149848 KB Output is correct
8 Correct 32 ms 149848 KB Output is correct
9 Correct 33 ms 149840 KB Output is correct
10 Correct 32 ms 149848 KB Output is correct
11 Correct 31 ms 149848 KB Output is correct
12 Correct 32 ms 149840 KB Output is correct
13 Correct 33 ms 149584 KB Output is correct
14 Correct 31 ms 149584 KB Output is correct
15 Correct 32 ms 149596 KB Output is correct
16 Correct 31 ms 149552 KB Output is correct
17 Correct 33 ms 150436 KB Output is correct
18 Correct 34 ms 150352 KB Output is correct
19 Correct 32 ms 150360 KB Output is correct
20 Correct 33 ms 150360 KB Output is correct
21 Correct 34 ms 150352 KB Output is correct
22 Correct 34 ms 150364 KB Output is correct
23 Correct 36 ms 152656 KB Output is correct
24 Correct 32 ms 150096 KB Output is correct
25 Correct 32 ms 149584 KB Output is correct
26 Correct 31 ms 149592 KB Output is correct
27 Correct 32 ms 153944 KB Output is correct
28 Correct 31 ms 149584 KB Output is correct
29 Correct 31 ms 149620 KB Output is correct
30 Correct 42 ms 152912 KB Output is correct
31 Correct 44 ms 152916 KB Output is correct
32 Correct 42 ms 152912 KB Output is correct
33 Correct 38 ms 153944 KB Output is correct
34 Correct 43 ms 152252 KB Output is correct
35 Correct 44 ms 152468 KB Output is correct
36 Correct 44 ms 154192 KB Output is correct
37 Correct 44 ms 152232 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 149584 KB Output is correct
2 Correct 31 ms 149844 KB Output is correct
3 Correct 31 ms 149840 KB Output is correct
4 Correct 31 ms 149848 KB Output is correct
5 Correct 31 ms 149596 KB Output is correct
6 Correct 32 ms 149816 KB Output is correct
7 Correct 31 ms 149848 KB Output is correct
8 Correct 32 ms 149848 KB Output is correct
9 Correct 33 ms 149840 KB Output is correct
10 Correct 32 ms 149848 KB Output is correct
11 Correct 31 ms 149848 KB Output is correct
12 Correct 32 ms 149840 KB Output is correct
13 Correct 33 ms 149584 KB Output is correct
14 Correct 31 ms 149584 KB Output is correct
15 Correct 32 ms 149596 KB Output is correct
16 Correct 31 ms 149552 KB Output is correct
17 Correct 33 ms 150436 KB Output is correct
18 Correct 34 ms 150352 KB Output is correct
19 Correct 32 ms 150360 KB Output is correct
20 Correct 33 ms 150360 KB Output is correct
21 Correct 34 ms 150352 KB Output is correct
22 Correct 34 ms 150364 KB Output is correct
23 Correct 36 ms 152656 KB Output is correct
24 Correct 32 ms 150096 KB Output is correct
25 Correct 42 ms 152912 KB Output is correct
26 Correct 44 ms 152916 KB Output is correct
27 Correct 42 ms 152912 KB Output is correct
28 Correct 38 ms 153944 KB Output is correct
29 Correct 43 ms 152252 KB Output is correct
30 Correct 44 ms 152468 KB Output is correct
31 Correct 44 ms 154192 KB Output is correct
32 Correct 44 ms 152232 KB Output is correct
33 Correct 32 ms 149584 KB Output is correct
34 Correct 31 ms 149592 KB Output is correct
35 Correct 32 ms 153944 KB Output is correct
36 Correct 31 ms 149584 KB Output is correct
37 Correct 31 ms 149620 KB Output is correct
38 Correct 118 ms 166992 KB Output is correct
39 Correct 108 ms 167248 KB Output is correct
40 Correct 115 ms 173624 KB Output is correct
41 Correct 100 ms 173240 KB Output is correct
42 Correct 189 ms 182096 KB Output is correct
43 Correct 203 ms 182064 KB Output is correct
44 Correct 190 ms 182180 KB Output is correct
45 Correct 179 ms 180352 KB Output is correct
46 Correct 105 ms 166736 KB Output is correct
47 Correct 124 ms 164432 KB Output is correct
48 Correct 223 ms 168448 KB Output is correct
49 Correct 225 ms 168784 KB Output is correct
50 Correct 115 ms 158800 KB Output is correct
51 Correct 120 ms 162388 KB Output is correct
52 Correct 192 ms 166736 KB Output is correct
53 Correct 200 ms 166992 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 160080 KB Output is correct
2 Correct 37 ms 158548 KB Output is correct
3 Correct 31 ms 149848 KB Output is correct
4 Correct 31 ms 149592 KB Output is correct
5 Correct 38 ms 162900 KB Output is correct
6 Correct 38 ms 162636 KB Output is correct
7 Correct 42 ms 163152 KB Output is correct
8 Correct 37 ms 161844 KB Output is correct
9 Correct 38 ms 161360 KB Output is correct
10 Correct 34 ms 154968 KB Output is correct
11 Correct 37 ms 157276 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 149584 KB Output is correct
2 Correct 31 ms 149592 KB Output is correct
3 Correct 32 ms 153944 KB Output is correct
4 Correct 31 ms 149584 KB Output is correct
5 Correct 31 ms 149620 KB Output is correct
6 Correct 31 ms 151640 KB Output is correct
7 Correct 497 ms 213584 KB Output is correct
8 Correct 1033 ms 266832 KB Output is correct
9 Correct 1034 ms 267556 KB Output is correct
10 Correct 1044 ms 267368 KB Output is correct
11 Correct 203 ms 173904 KB Output is correct
12 Correct 389 ms 195664 KB Output is correct
13 Correct 417 ms 198928 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 149584 KB Output is correct
2 Correct 31 ms 149844 KB Output is correct
3 Correct 31 ms 149840 KB Output is correct
4 Correct 31 ms 149848 KB Output is correct
5 Correct 31 ms 149596 KB Output is correct
6 Correct 32 ms 149816 KB Output is correct
7 Correct 31 ms 149848 KB Output is correct
8 Correct 32 ms 149848 KB Output is correct
9 Correct 33 ms 149840 KB Output is correct
10 Correct 32 ms 149848 KB Output is correct
11 Correct 31 ms 149848 KB Output is correct
12 Correct 32 ms 149840 KB Output is correct
13 Correct 33 ms 149584 KB Output is correct
14 Correct 31 ms 149584 KB Output is correct
15 Correct 32 ms 149596 KB Output is correct
16 Correct 31 ms 149552 KB Output is correct
17 Correct 33 ms 150436 KB Output is correct
18 Correct 34 ms 150352 KB Output is correct
19 Correct 32 ms 150360 KB Output is correct
20 Correct 33 ms 150360 KB Output is correct
21 Correct 34 ms 150352 KB Output is correct
22 Correct 34 ms 150364 KB Output is correct
23 Correct 36 ms 152656 KB Output is correct
24 Correct 32 ms 150096 KB Output is correct
25 Correct 42 ms 152912 KB Output is correct
26 Correct 44 ms 152916 KB Output is correct
27 Correct 42 ms 152912 KB Output is correct
28 Correct 38 ms 153944 KB Output is correct
29 Correct 43 ms 152252 KB Output is correct
30 Correct 44 ms 152468 KB Output is correct
31 Correct 44 ms 154192 KB Output is correct
32 Correct 44 ms 152232 KB Output is correct
33 Correct 118 ms 166992 KB Output is correct
34 Correct 108 ms 167248 KB Output is correct
35 Correct 115 ms 173624 KB Output is correct
36 Correct 100 ms 173240 KB Output is correct
37 Correct 189 ms 182096 KB Output is correct
38 Correct 203 ms 182064 KB Output is correct
39 Correct 190 ms 182180 KB Output is correct
40 Correct 179 ms 180352 KB Output is correct
41 Correct 105 ms 166736 KB Output is correct
42 Correct 124 ms 164432 KB Output is correct
43 Correct 223 ms 168448 KB Output is correct
44 Correct 225 ms 168784 KB Output is correct
45 Correct 115 ms 158800 KB Output is correct
46 Correct 120 ms 162388 KB Output is correct
47 Correct 192 ms 166736 KB Output is correct
48 Correct 200 ms 166992 KB Output is correct
49 Correct 37 ms 160080 KB Output is correct
50 Correct 37 ms 158548 KB Output is correct
51 Correct 31 ms 149848 KB Output is correct
52 Correct 31 ms 149592 KB Output is correct
53 Correct 38 ms 162900 KB Output is correct
54 Correct 38 ms 162636 KB Output is correct
55 Correct 42 ms 163152 KB Output is correct
56 Correct 37 ms 161844 KB Output is correct
57 Correct 38 ms 161360 KB Output is correct
58 Correct 34 ms 154968 KB Output is correct
59 Correct 37 ms 157276 KB Output is correct
60 Correct 31 ms 151640 KB Output is correct
61 Correct 497 ms 213584 KB Output is correct
62 Correct 1033 ms 266832 KB Output is correct
63 Correct 1034 ms 267556 KB Output is correct
64 Correct 1044 ms 267368 KB Output is correct
65 Correct 203 ms 173904 KB Output is correct
66 Correct 389 ms 195664 KB Output is correct
67 Correct 417 ms 198928 KB Output is correct
68 Correct 32 ms 149584 KB Output is correct
69 Correct 31 ms 149592 KB Output is correct
70 Correct 32 ms 153944 KB Output is correct
71 Correct 31 ms 149584 KB Output is correct
72 Correct 31 ms 149620 KB Output is correct
73 Correct 1235 ms 260080 KB Output is correct
74 Correct 1132 ms 260168 KB Output is correct
75 Correct 1236 ms 339564 KB Output is correct
76 Correct 1033 ms 339428 KB Output is correct
77 Correct 2563 ms 542188 KB Output is correct
78 Correct 1622 ms 270568 KB Output is correct
79 Correct 1735 ms 265284 KB Output is correct
80 Correct 2779 ms 332512 KB Output is correct
81 Correct 1650 ms 274460 KB Output is correct
82 Correct 2314 ms 298216 KB Output is correct
83 Correct 2839 ms 336380 KB Output is correct
84 Correct 1540 ms 256608 KB Output is correct
85 Correct 2669 ms 316280 KB Output is correct
86 Correct 2554 ms 311136 KB Output is correct
87 Correct 1480 ms 385292 KB Output is correct
88 Correct 2500 ms 541996 KB Output is correct
89 Correct 2509 ms 542324 KB Output is correct
90 Correct 2528 ms 542200 KB Output is correct