# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

143394 | 2019-08-13T23:17:28 Z | model_code | Rectangles (IOI19_rect) | C++17 | 2412 ms | 323592 KB |

// model_solution/rect-mruxim-n2lg.cpp // ... ... .. ....! // ... ....... .... ...! #include<bits/stdc++.h> using namespace std; #define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i) #define fer(i, a, b) for(int i = (int)(a), i##__b = (int)(b); i < i##__b; ++i) #define rof(i, b, a) for(int i = (int)(b), i##__a = (int)(a); i-- > i##__a; ) #define sz(x) (int((x).size())) #define pb push_back #define all(x) (x).begin(), (x).end() #define X first #define Y second //#define endl '\n' template<class P, class Q> inline void smin(P &a, Q b) { if (b < a) a = b; } template<class P, class Q> inline void smax(P &a, Q b) { if (a < b) a = b; } typedef long long ll; typedef pair<int, int> pii; //////////////////////////////////////////////////////////////////////////////// const int maxn = 3000 + 10; int n, m; vector<vector<int>> H; short L[maxn][maxn], R[maxn][maxn], U[maxn][maxn], D[maxn][maxn]; short UL[maxn][maxn], DL[maxn][maxn], LU[maxn][maxn], RU[maxn][maxn]; vector<ll> v; void precalc() { short st[maxn]; rep(i, n) { int t = 0; rep(j, m) { while(t && H[i][j] > H[i][st[t-1]]) t--; L[i][j] = (t ? st[t-1] : -1); st[t++] = j; } } rep(i, n) { int t = 0; rof(j, m, 0) { while(t && H[i][j] > H[i][st[t-1]]) t--; R[i][j] = (t ? st[t-1] : -1); st[t++] = j; } } rep(j, m) { int t = 0; rep(i, n) { while(t && H[i][j] > H[st[t-1]][j]) t--; U[i][j] = (t ? st[t-1] : -1); st[t++] = i; } } rep(j, m) { int t = 0; rof(i, n, 0) { while(t && H[i][j] > H[st[t-1]][j]) t--; D[i][j] = (t ? st[t-1] : -1); st[t++] = i; } } rep(j, m) rep(i, n) { if(U[i][j] != -1) { if(j > 0 && U[i][j] == U[i][j-1]) UL[i][j] = UL[i][j-1]; else if(j > 0 && i == D[U[i][j]][j-1]) UL[i][j] = DL[U[i][j]][j-1]; else UL[i][j] = j; } if(D[i][j] != -1) { if(j > 0 && D[i][j] == D[i][j-1]) DL[i][j] = DL[i][j-1]; else if(j > 0 && i == U[D[i][j]][j-1]) DL[i][j] = UL[D[i][j]][j-1]; else DL[i][j] = j; } } rep(i, n) rep(j, m) { if(L[i][j] != -1) { if(i > 0 && L[i][j] == L[i-1][j]) LU[i][j] = LU[i-1][j]; else if(i > 0 && j == R[i-1][L[i][j]]) LU[i][j] = RU[i-1][L[i][j]]; else LU[i][j] = i; } if(R[i][j] != -1) { if(i > 0 && R[i][j] == R[i-1][j]) RU[i][j] = RU[i-1][j]; else if(i > 0 && j == L[i-1][R[i][j]]) RU[i][j] = LU[i-1][R[i][j]]; else RU[i][j] = i; } } } void check(int i1, int i2, int j1, int j2) { if(i2 < i1 || j2 < j1) return; if(!((R[i2][j1-1]-1 == j2 && RU[i2][j1-1] <= i1) || (L[i2][j2+1]+1 == j1 && LU[i2][j2+1] <= i1))) return; if(!((D[i1-1][j2]-1 == i2 && DL[i1-1][j2] <= j1) || (U[i2+1][j2]+1 == i1 && UL[i2+1][j2] <= j1))) return; v.pb((((ll)i1 * maxn + i2) * maxn + j1) * maxn + j2); } int count_rectangles(vector<vector<int>> _H) { H = _H; n = sz(H); m = sz(H[0]); precalc(); fer(i, 1, n-1) fer(j, 1, m-1) { if(U[i+1][j] != -1 && L[i][j+1] != -1) check(U[i+1][j]+1, i, L[i][j+1]+1, j); if(U[i+1][j] != -1 && R[i][j-1] != -1) check(U[i+1][j]+1, i, j, R[i][j-1]-1); if(D[i-1][j] != -1 && L[i][j+1] != -1) check(i, D[i-1][j]-1, L[i][j+1]+1, j); if(D[i-1][j] != -1 && R[i][j-1] != -1) check(i, D[i-1][j]-1, j, R[i][j-1]-1); if(D[i-1][j] != -1 && R[D[i-1][j]-1][j-1] != -1) check(i, D[i-1][j]-1, j, R[D[i-1][j]-1][j-1]-1); if(D[i-1][j] != -1 && L[D[i-1][j]-1][j+1] != -1) check(i, D[i-1][j]-1, L[D[i-1][j]-1][j+1]+1, j); } sort(all(v)); v.resize(unique(all(v)) - v.begin()); return sz(v); }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 504 KB | Output is correct |

2 | Correct | 3 ms | 1400 KB | Output is correct |

3 | Correct | 3 ms | 1400 KB | Output is correct |

4 | Correct | 3 ms | 1400 KB | Output is correct |

5 | Correct | 3 ms | 1400 KB | Output is correct |

6 | Correct | 3 ms | 1400 KB | Output is correct |

7 | Correct | 3 ms | 1400 KB | Output is correct |

8 | Correct | 2 ms | 760 KB | Output is correct |

9 | Correct | 3 ms | 1400 KB | Output is correct |

10 | Correct | 3 ms | 1400 KB | Output is correct |

11 | Correct | 3 ms | 1400 KB | Output is correct |

12 | Correct | 3 ms | 1272 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 632 KB | Output is correct |

15 | Correct | 2 ms | 632 KB | Output is correct |

16 | Correct | 2 ms | 504 KB | Output is correct |

17 | Correct | 2 ms | 376 KB | Output is correct |

18 | Correct | 2 ms | 376 KB | Output is correct |

19 | Correct | 3 ms | 1404 KB | Output is correct |

20 | Correct | 3 ms | 1272 KB | Output is correct |

21 | Correct | 2 ms | 632 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 504 KB | Output is correct |

2 | Correct | 3 ms | 1400 KB | Output is correct |

3 | Correct | 3 ms | 1400 KB | Output is correct |

4 | Correct | 3 ms | 1400 KB | Output is correct |

5 | Correct | 3 ms | 1400 KB | Output is correct |

6 | Correct | 3 ms | 1400 KB | Output is correct |

7 | Correct | 3 ms | 1400 KB | Output is correct |

8 | Correct | 2 ms | 760 KB | Output is correct |

9 | Correct | 3 ms | 1400 KB | Output is correct |

10 | Correct | 3 ms | 1400 KB | Output is correct |

11 | Correct | 3 ms | 1400 KB | Output is correct |

12 | Correct | 3 ms | 1272 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 632 KB | Output is correct |

15 | Correct | 2 ms | 632 KB | Output is correct |

16 | Correct | 2 ms | 504 KB | Output is correct |

17 | Correct | 5 ms | 3320 KB | Output is correct |

18 | Correct | 5 ms | 3320 KB | Output is correct |

19 | Correct | 5 ms | 3324 KB | Output is correct |

20 | Correct | 5 ms | 3064 KB | Output is correct |

21 | Correct | 5 ms | 3192 KB | Output is correct |

22 | Correct | 5 ms | 3192 KB | Output is correct |

23 | Correct | 5 ms | 3192 KB | Output is correct |

24 | Correct | 5 ms | 3064 KB | Output is correct |

25 | Correct | 2 ms | 376 KB | Output is correct |

26 | Correct | 2 ms | 376 KB | Output is correct |

27 | Correct | 3 ms | 1404 KB | Output is correct |

28 | Correct | 3 ms | 1272 KB | Output is correct |

29 | Correct | 2 ms | 632 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 504 KB | Output is correct |

2 | Correct | 3 ms | 1400 KB | Output is correct |

3 | Correct | 3 ms | 1400 KB | Output is correct |

4 | Correct | 3 ms | 1400 KB | Output is correct |

5 | Correct | 3 ms | 1400 KB | Output is correct |

6 | Correct | 3 ms | 1400 KB | Output is correct |

7 | Correct | 3 ms | 1400 KB | Output is correct |

8 | Correct | 2 ms | 760 KB | Output is correct |

9 | Correct | 3 ms | 1400 KB | Output is correct |

10 | Correct | 3 ms | 1400 KB | Output is correct |

11 | Correct | 3 ms | 1400 KB | Output is correct |

12 | Correct | 3 ms | 1272 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 632 KB | Output is correct |

15 | Correct | 2 ms | 632 KB | Output is correct |

16 | Correct | 2 ms | 504 KB | Output is correct |

17 | Correct | 5 ms | 3320 KB | Output is correct |

18 | Correct | 5 ms | 3320 KB | Output is correct |

19 | Correct | 5 ms | 3324 KB | Output is correct |

20 | Correct | 5 ms | 3064 KB | Output is correct |

21 | Correct | 5 ms | 3192 KB | Output is correct |

22 | Correct | 5 ms | 3192 KB | Output is correct |

23 | Correct | 5 ms | 3192 KB | Output is correct |

24 | Correct | 5 ms | 3064 KB | Output is correct |

25 | Correct | 14 ms | 9076 KB | Output is correct |

26 | Correct | 15 ms | 9084 KB | Output is correct |

27 | Correct | 15 ms | 9076 KB | Output is correct |

28 | Correct | 14 ms | 8184 KB | Output is correct |

29 | Correct | 16 ms | 8312 KB | Output is correct |

30 | Correct | 16 ms | 8184 KB | Output is correct |

31 | Correct | 16 ms | 8312 KB | Output is correct |

32 | Correct | 15 ms | 8184 KB | Output is correct |

33 | Correct | 2 ms | 376 KB | Output is correct |

34 | Correct | 2 ms | 376 KB | Output is correct |

35 | Correct | 3 ms | 1404 KB | Output is correct |

36 | Correct | 3 ms | 1272 KB | Output is correct |

37 | Correct | 2 ms | 632 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 504 KB | Output is correct |

2 | Correct | 3 ms | 1400 KB | Output is correct |

3 | Correct | 3 ms | 1400 KB | Output is correct |

4 | Correct | 3 ms | 1400 KB | Output is correct |

5 | Correct | 3 ms | 1400 KB | Output is correct |

6 | Correct | 3 ms | 1400 KB | Output is correct |

7 | Correct | 3 ms | 1400 KB | Output is correct |

8 | Correct | 2 ms | 760 KB | Output is correct |

9 | Correct | 3 ms | 1400 KB | Output is correct |

10 | Correct | 3 ms | 1400 KB | Output is correct |

11 | Correct | 3 ms | 1400 KB | Output is correct |

12 | Correct | 3 ms | 1272 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 632 KB | Output is correct |

15 | Correct | 2 ms | 632 KB | Output is correct |

16 | Correct | 2 ms | 504 KB | Output is correct |

17 | Correct | 5 ms | 3320 KB | Output is correct |

18 | Correct | 5 ms | 3320 KB | Output is correct |

19 | Correct | 5 ms | 3324 KB | Output is correct |

20 | Correct | 5 ms | 3064 KB | Output is correct |

21 | Correct | 5 ms | 3192 KB | Output is correct |

22 | Correct | 5 ms | 3192 KB | Output is correct |

23 | Correct | 5 ms | 3192 KB | Output is correct |

24 | Correct | 5 ms | 3064 KB | Output is correct |

25 | Correct | 14 ms | 9076 KB | Output is correct |

26 | Correct | 15 ms | 9084 KB | Output is correct |

27 | Correct | 15 ms | 9076 KB | Output is correct |

28 | Correct | 14 ms | 8184 KB | Output is correct |

29 | Correct | 16 ms | 8312 KB | Output is correct |

30 | Correct | 16 ms | 8184 KB | Output is correct |

31 | Correct | 16 ms | 8312 KB | Output is correct |

32 | Correct | 15 ms | 8184 KB | Output is correct |

33 | Correct | 80 ms | 35360 KB | Output is correct |

34 | Correct | 80 ms | 35320 KB | Output is correct |

35 | Correct | 78 ms | 35328 KB | Output is correct |

36 | Correct | 77 ms | 35320 KB | Output is correct |

37 | Correct | 157 ms | 44804 KB | Output is correct |

38 | Correct | 160 ms | 44668 KB | Output is correct |

39 | Correct | 159 ms | 44768 KB | Output is correct |

40 | Correct | 149 ms | 42228 KB | Output is correct |

41 | Correct | 109 ms | 37360 KB | Output is correct |

42 | Correct | 124 ms | 38380 KB | Output is correct |

43 | Correct | 146 ms | 38508 KB | Output is correct |

44 | Correct | 154 ms | 38412 KB | Output is correct |

45 | Correct | 84 ms | 30704 KB | Output is correct |

46 | Correct | 68 ms | 19440 KB | Output is correct |

47 | Correct | 146 ms | 38440 KB | Output is correct |

48 | Correct | 149 ms | 38504 KB | Output is correct |

49 | Correct | 2 ms | 376 KB | Output is correct |

50 | Correct | 2 ms | 376 KB | Output is correct |

51 | Correct | 3 ms | 1404 KB | Output is correct |

52 | Correct | 3 ms | 1272 KB | Output is correct |

53 | Correct | 2 ms | 632 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 3 ms | 660 KB | Output is correct |

2 | Correct | 3 ms | 632 KB | Output is correct |

3 | Correct | 2 ms | 504 KB | Output is correct |

4 | Correct | 2 ms | 376 KB | Output is correct |

5 | Correct | 3 ms | 632 KB | Output is correct |

6 | Correct | 3 ms | 632 KB | Output is correct |

7 | Correct | 3 ms | 632 KB | Output is correct |

8 | Correct | 3 ms | 632 KB | Output is correct |

9 | Correct | 3 ms | 632 KB | Output is correct |

10 | Correct | 2 ms | 376 KB | Output is correct |

11 | Correct | 3 ms | 504 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 632 KB | Output is correct |

2 | Correct | 638 ms | 100692 KB | Output is correct |

3 | Correct | 1495 ms | 207532 KB | Output is correct |

4 | Correct | 1474 ms | 208564 KB | Output is correct |

5 | Correct | 1493 ms | 208600 KB | Output is correct |

6 | Correct | 467 ms | 94840 KB | Output is correct |

7 | Correct | 1038 ms | 187344 KB | Output is correct |

8 | Correct | 1099 ms | 192004 KB | Output is correct |

9 | Correct | 2 ms | 376 KB | Output is correct |

10 | Correct | 2 ms | 376 KB | Output is correct |

11 | Correct | 3 ms | 1404 KB | Output is correct |

12 | Correct | 3 ms | 1272 KB | Output is correct |

13 | Correct | 2 ms | 632 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 504 KB | Output is correct |

2 | Correct | 3 ms | 1400 KB | Output is correct |

3 | Correct | 3 ms | 1400 KB | Output is correct |

4 | Correct | 3 ms | 1400 KB | Output is correct |

5 | Correct | 3 ms | 1400 KB | Output is correct |

6 | Correct | 3 ms | 1400 KB | Output is correct |

7 | Correct | 3 ms | 1400 KB | Output is correct |

8 | Correct | 2 ms | 760 KB | Output is correct |

9 | Correct | 3 ms | 1400 KB | Output is correct |

10 | Correct | 3 ms | 1400 KB | Output is correct |

11 | Correct | 3 ms | 1400 KB | Output is correct |

12 | Correct | 3 ms | 1272 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 632 KB | Output is correct |

15 | Correct | 2 ms | 632 KB | Output is correct |

16 | Correct | 2 ms | 504 KB | Output is correct |

17 | Correct | 5 ms | 3320 KB | Output is correct |

18 | Correct | 5 ms | 3320 KB | Output is correct |

19 | Correct | 5 ms | 3324 KB | Output is correct |

20 | Correct | 5 ms | 3064 KB | Output is correct |

21 | Correct | 5 ms | 3192 KB | Output is correct |

22 | Correct | 5 ms | 3192 KB | Output is correct |

23 | Correct | 5 ms | 3192 KB | Output is correct |

24 | Correct | 5 ms | 3064 KB | Output is correct |

25 | Correct | 14 ms | 9076 KB | Output is correct |

26 | Correct | 15 ms | 9084 KB | Output is correct |

27 | Correct | 15 ms | 9076 KB | Output is correct |

28 | Correct | 14 ms | 8184 KB | Output is correct |

29 | Correct | 16 ms | 8312 KB | Output is correct |

30 | Correct | 16 ms | 8184 KB | Output is correct |

31 | Correct | 16 ms | 8312 KB | Output is correct |

32 | Correct | 15 ms | 8184 KB | Output is correct |

33 | Correct | 80 ms | 35360 KB | Output is correct |

34 | Correct | 80 ms | 35320 KB | Output is correct |

35 | Correct | 78 ms | 35328 KB | Output is correct |

36 | Correct | 77 ms | 35320 KB | Output is correct |

37 | Correct | 157 ms | 44804 KB | Output is correct |

38 | Correct | 160 ms | 44668 KB | Output is correct |

39 | Correct | 159 ms | 44768 KB | Output is correct |

40 | Correct | 149 ms | 42228 KB | Output is correct |

41 | Correct | 109 ms | 37360 KB | Output is correct |

42 | Correct | 124 ms | 38380 KB | Output is correct |

43 | Correct | 146 ms | 38508 KB | Output is correct |

44 | Correct | 154 ms | 38412 KB | Output is correct |

45 | Correct | 84 ms | 30704 KB | Output is correct |

46 | Correct | 68 ms | 19440 KB | Output is correct |

47 | Correct | 146 ms | 38440 KB | Output is correct |

48 | Correct | 149 ms | 38504 KB | Output is correct |

49 | Correct | 3 ms | 660 KB | Output is correct |

50 | Correct | 3 ms | 632 KB | Output is correct |

51 | Correct | 2 ms | 504 KB | Output is correct |

52 | Correct | 2 ms | 376 KB | Output is correct |

53 | Correct | 3 ms | 632 KB | Output is correct |

54 | Correct | 3 ms | 632 KB | Output is correct |

55 | Correct | 3 ms | 632 KB | Output is correct |

56 | Correct | 3 ms | 632 KB | Output is correct |

57 | Correct | 3 ms | 632 KB | Output is correct |

58 | Correct | 2 ms | 376 KB | Output is correct |

59 | Correct | 3 ms | 504 KB | Output is correct |

60 | Correct | 2 ms | 632 KB | Output is correct |

61 | Correct | 638 ms | 100692 KB | Output is correct |

62 | Correct | 1495 ms | 207532 KB | Output is correct |

63 | Correct | 1474 ms | 208564 KB | Output is correct |

64 | Correct | 1493 ms | 208600 KB | Output is correct |

65 | Correct | 467 ms | 94840 KB | Output is correct |

66 | Correct | 1038 ms | 187344 KB | Output is correct |

67 | Correct | 1099 ms | 192004 KB | Output is correct |

68 | Correct | 1237 ms | 190328 KB | Output is correct |

69 | Correct | 1240 ms | 190328 KB | Output is correct |

70 | Correct | 1115 ms | 190100 KB | Output is correct |

71 | Correct | 1129 ms | 190320 KB | Output is correct |

72 | Correct | 2388 ms | 323592 KB | Output is correct |

73 | Correct | 1142 ms | 131868 KB | Output is correct |

74 | Correct | 1331 ms | 181376 KB | Output is correct |

75 | Correct | 1951 ms | 224768 KB | Output is correct |

76 | Correct | 1191 ms | 131896 KB | Output is correct |

77 | Correct | 1663 ms | 210320 KB | Output is correct |

78 | Correct | 2049 ms | 224968 KB | Output is correct |

79 | Correct | 1156 ms | 132048 KB | Output is correct |

80 | Correct | 2019 ms | 225108 KB | Output is correct |

81 | Correct | 1947 ms | 219836 KB | Output is correct |

82 | Correct | 1377 ms | 228392 KB | Output is correct |

83 | Correct | 2412 ms | 323348 KB | Output is correct |

84 | Correct | 2380 ms | 323396 KB | Output is correct |

85 | Correct | 2359 ms | 323492 KB | Output is correct |

86 | Correct | 2 ms | 376 KB | Output is correct |

87 | Correct | 2 ms | 376 KB | Output is correct |

88 | Correct | 3 ms | 1404 KB | Output is correct |

89 | Correct | 3 ms | 1272 KB | Output is correct |

90 | Correct | 2 ms | 632 KB | Output is correct |