oj.uz

Submission #824775

# Submission time Handle Problem Language Result Execution time Memory
824775 2023-08-14T09:57:57 Z erray Rectangles (IOI19_rect) C++17
100 / 100
 2756 ms 846248 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

struct Fenwick {
  vector<short> sum;
  int n;
  Fenwick(int _n) : n(_n) {
    sum.resize(n + 1);
  }
  void modify(int x, int d) {
    x += 1;
    while (x <= n) {
      sum[x] += d;
      x += x & -x;
    }
  }
  int get(int x) {
    x += 1;
    int res = 0;
    while (x > 0) {
      res += sum[x];
      x -= x & -x;
    }
    return res;
  }
};

using RT = vector<vector<vector<array<short, 2>>>>;
RT calc_ranges(vector<vector<int>> A, bool inv) {
	int N = int(A.size());
  int M = int(A[0].size());
  int sn = N, sm = M;
  if (inv) {
    swap(sn, sm);
  }
  RT res(sn, vector<vector<array<short, 2>>>(sm));
  vector<vector<array<int, 2>>> last(M, vector<array<int, 2>>(M, array<int, 2>{}));
  for (int i = N - 1; i >= 0; --i) {
    auto Add = [&](int l, int r) {
      if (l + 1 == r) {
        return;
      }
      if (last[l][r][0] != i + 1) {
        last[l][r][1] = i;
      }
      last[l][r][0] = i;
      (inv ? res[l][i] : res[i][l]).push_back({r, last[l][r][1]});
    };
    vector<int> st;
    for (int j = M - 1; j >= 0; --j) {
      bool eq = false;
      while (!st.empty() && A[i][st.back()] <= A[i][j]) {
        eq |= A[i][st.back()] == A[i][j];
        Add(j, st.back());
        st.pop_back();
      }
      if (!st.empty() && !eq) {
        Add(j, st.back());
      }
      st.push_back(j);
    }
  }
  return res;
}

long long count_rectangles(std::vector<std::vector<int> > A) {
	int N = int(A.size());
  int M = int(A[0].size());
  auto row_ranges = calc_ranges(A, false);  
  vector<vector<int>> temp_A(M, vector<int>(N));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      temp_A[j][i] = A[i][j];
    }
  }
  auto col_ranges = calc_ranges(temp_A, true);
  /*
  auto temp = calc_ranges(temp_A);
  RT col_ranges(N, vector<vector<array<short, 2>>>(M));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      col_ranges[i][j] = temp[j][i];
    }
  }
  */
  vector<Fenwick> fenw(N, Fenwick(N));
  long long ans = 0;
  for (int l = 0; l < M - 1; ++l) {
    vector<vector<array<short, 2>>> query(M);
    for (int i = 0; i < N; ++i) {
      for (auto[r, ending] : row_ranges[i][l]) {
        query[r].push_back({i, ending});
      }
    }
    vector<vector<array<short, 2>>> rem(M);
    for (int i = 0; i < N; ++i) {
      for (auto[d, ending] : col_ranges[i][l + 1]) {
        fenw[i + 1].modify(d - 1, +1);
        rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
      }
    }
    for (int r = l + 2; r < M; ++r) {
      for (auto[u, d] : query[r]) {
        ans += fenw[u].get(d);
      }
      for (auto[u, d] : rem[r]) {
        fenw[u].modify(d, -1);
      }
    }
    debug(ans);
  }
  return ans;
}

Compilation message

rect.cpp: In lambda function:
rect.cpp:55:48: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   55 |       (inv ? res[l][i] : res[i][l]).push_back({r, last[l][r][1]});
      |                                                ^
rect.cpp:55:65: warning: narrowing conversion of '(&(&(& last)->std::vector<std::vector<std::array<int, 2> > >::operator[](((std::vector<std::vector<std::array<int, 2> > >::size_type)l)))->std::vector<std::array<int, 2> >::operator[](((std::vector<std::array<int, 2> >::size_type)r)))->std::array<int, 2>::operator[](1)' from 'std::array<int, 2>::value_type' {aka 'int'} to 'short int' [-Wnarrowing]
   55 |       (inv ? res[l][i] : res[i][l]).push_back({r, last[l][r][1]});
      |                                                                 ^
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:100:29: warning: narrowing conversion of 'i' from 'int' to 'short int' [-Wnarrowing]
  100 |         query[r].push_back({i, ending});
      |                             ^
rect.cpp:107:50: warning: narrowing conversion of '(i + 1)' from 'int' to 'short int' [-Wnarrowing]
  107 |         rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
      |                                                ~~^~~
rect.cpp:107:57: warning: narrowing conversion of '(((int)d) - 1)' from 'int' to 'short int' [-Wnarrowing]
  107 |         rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
      |                                                       ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 2 ms 1108 KB Output is correct
25 Correct 1 ms 852 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 1 ms 596 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 2 ms 1108 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 3 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 8 ms 5588 KB Output is correct
31 Correct 8 ms 5572 KB Output is correct
32 Correct 10 ms 5588 KB Output is correct
33 Correct 6 ms 3924 KB Output is correct
34 Correct 10 ms 4424 KB Output is correct
35 Correct 11 ms 4432 KB Output is correct
36 Correct 10 ms 4308 KB Output is correct
37 Correct 10 ms 4156 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 2 ms 1108 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 3 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 8 ms 5588 KB Output is correct
26 Correct 8 ms 5572 KB Output is correct
27 Correct 10 ms 5588 KB Output is correct
28 Correct 6 ms 3924 KB Output is correct
29 Correct 10 ms 4424 KB Output is correct
30 Correct 11 ms 4432 KB Output is correct
31 Correct 10 ms 4308 KB Output is correct
32 Correct 10 ms 4156 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 118 ms 50220 KB Output is correct
39 Correct 82 ms 44328 KB Output is correct
40 Correct 97 ms 44320 KB Output is correct
41 Correct 61 ms 38084 KB Output is correct
42 Correct 147 ms 65740 KB Output is correct
43 Correct 145 ms 65472 KB Output is correct
44 Correct 141 ms 65636 KB Output is correct
45 Correct 133 ms 61128 KB Output is correct
46 Correct 87 ms 42740 KB Output is correct
47 Correct 95 ms 45188 KB Output is correct
48 Correct 150 ms 50764 KB Output is correct
49 Correct 158 ms 50768 KB Output is correct
50 Correct 83 ms 27732 KB Output is correct
51 Correct 78 ms 24592 KB Output is correct
52 Correct 144 ms 49488 KB Output is correct
53 Correct 150 ms 49624 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 49748 KB Output is correct
2 Correct 33 ms 36056 KB Output is correct
3 Correct 44 ms 49620 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 46 ms 49672 KB Output is correct
6 Correct 47 ms 49680 KB Output is correct
7 Correct 46 ms 49620 KB Output is correct
8 Correct 46 ms 49676 KB Output is correct
9 Correct 50 ms 49612 KB Output is correct
10 Correct 45 ms 49352 KB Output is correct
11 Correct 51 ms 49512 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 531 ms 236624 KB Output is correct
8 Correct 1231 ms 535904 KB Output is correct
9 Correct 1236 ms 538768 KB Output is correct
10 Correct 1243 ms 539012 KB Output is correct
11 Correct 269 ms 205792 KB Output is correct
12 Correct 467 ms 416900 KB Output is correct
13 Correct 532 ms 441312 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 2 ms 1108 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 3 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 8 ms 5588 KB Output is correct
26 Correct 8 ms 5572 KB Output is correct
27 Correct 10 ms 5588 KB Output is correct
28 Correct 6 ms 3924 KB Output is correct
29 Correct 10 ms 4424 KB Output is correct
30 Correct 11 ms 4432 KB Output is correct
31 Correct 10 ms 4308 KB Output is correct
32 Correct 10 ms 4156 KB Output is correct
33 Correct 118 ms 50220 KB Output is correct
34 Correct 82 ms 44328 KB Output is correct
35 Correct 97 ms 44320 KB Output is correct
36 Correct 61 ms 38084 KB Output is correct
37 Correct 147 ms 65740 KB Output is correct
38 Correct 145 ms 65472 KB Output is correct
39 Correct 141 ms 65636 KB Output is correct
40 Correct 133 ms 61128 KB Output is correct
41 Correct 87 ms 42740 KB Output is correct
42 Correct 95 ms 45188 KB Output is correct
43 Correct 150 ms 50764 KB Output is correct
44 Correct 158 ms 50768 KB Output is correct
45 Correct 83 ms 27732 KB Output is correct
46 Correct 78 ms 24592 KB Output is correct
47 Correct 144 ms 49488 KB Output is correct
48 Correct 150 ms 49624 KB Output is correct
49 Correct 48 ms 49748 KB Output is correct
50 Correct 33 ms 36056 KB Output is correct
51 Correct 44 ms 49620 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 46 ms 49672 KB Output is correct
54 Correct 47 ms 49680 KB Output is correct
55 Correct 46 ms 49620 KB Output is correct
56 Correct 46 ms 49676 KB Output is correct
57 Correct 50 ms 49612 KB Output is correct
58 Correct 45 ms 49352 KB Output is correct
59 Correct 51 ms 49512 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 531 ms 236624 KB Output is correct
62 Correct 1231 ms 535904 KB Output is correct
63 Correct 1236 ms 538768 KB Output is correct
64 Correct 1243 ms 539012 KB Output is correct
65 Correct 269 ms 205792 KB Output is correct
66 Correct 467 ms 416900 KB Output is correct
67 Correct 532 ms 441312 KB Output is correct
68 Correct 0 ms 212 KB Output is correct
69 Correct 0 ms 212 KB Output is correct
70 Correct 0 ms 340 KB Output is correct
71 Correct 0 ms 340 KB Output is correct
72 Correct 0 ms 212 KB Output is correct
73 Correct 1983 ms 636868 KB Output is correct
74 Correct 1414 ms 555884 KB Output is correct
75 Correct 1383 ms 555864 KB Output is correct
76 Correct 879 ms 475132 KB Output is correct
77 Correct 2490 ms 843416 KB Output is correct
78 Correct 1302 ms 387252 KB Output is correct
79 Correct 1393 ms 428684 KB Output is correct
80 Correct 2433 ms 646608 KB Output is correct
81 Correct 1349 ms 379884 KB Output is correct
82 Correct 1832 ms 535600 KB Output is correct
83 Correct 2290 ms 662836 KB Output is correct
84 Correct 1273 ms 386528 KB Output is correct
85 Correct 2170 ms 644004 KB Output is correct
86 Correct 2120 ms 624368 KB Output is correct
87 Correct 1402 ms 529792 KB Output is correct
88 Correct 2756 ms 846248 KB Output is correct
89 Correct 2534 ms 841520 KB Output is correct
90 Correct 2563 ms 841136 KB Output is correct