답안 #844763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844763	2023-09-05T20:37:00 Z	qthang2k11	Rectangles (IOI19_rect)	C++17	100 / 100	1990 ms	564236 KB

rect

// [+] https://oj.uz/submission/286084
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int N = 2505;
 
int lh[N], rh[N], lw[N], rw[N], a[N][N];
pair<int, int> range[N][N];
 
enum class EventType {
  add,
  get
};
 
struct Event {
  EventType type;
  int r, c;
  
  Event() = default;
  Event(EventType type, int r, int c):
    type(type), r(r), c(c) {}
  
  bool operator < (const Event &other) const {
    return tie(r, type) < tie(other.r, other.type);
  }
};
 
vector<Event> events[N][N];
 
struct FenwickTree {
  int BIT[N], n = N - 1, all = 0;
  
  FenwickTree() = default;
  FenwickTree(int n): n(n) {}
  
  void update(int x, int w) {
    for (; x <= n; x += x & -x)
      BIT[x] += w;
    all += w;
  }
  
  int pref(int x) {
    int ans = 0;
    for (; x > 0; x -= x & -x)
      ans += BIT[x];
    return ans;
  }
  
  int suff(int x) {
    return all - pref(x - 1);
  }
} cnt;
 
ll count_rectangles(vector<vector<int>> b) {
  int m = b.size(), n = b[0].size();
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      a[i][j] = b[i - 1][j - 1];
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      range[i][j] = {-1, -1};
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      lw[j] = j - 1;
      while (lw[j] > 0 && a[i][j] >= a[i][lw[j]])
        lw[j] = lw[lw[j]];
    }
    for (int j = n; j > 0; j--) {
      rw[j] = j + 1;
      while (rw[j] <= n && a[i][j] >= a[i][rw[j]])
        rw[j] = rw[rw[j]];
    }
    for (int j = 1; j <= n; j++) {
      int l = lw[j] + 1, r = rw[j] - 1;
      if (1 < l && l <= r && r < n && range[l][r].second != i) {
        if (range[l][r].second == i - 1)
          range[l][r].second++;
        else range[l][r] = {i, i};
        int len = range[l][r].second - range[l][r].first + 1;
        events[i][r].emplace_back(EventType::get, len, r - l + 1);
      }
    }
  }
  for (int i = 1; i <= m; i++)
    for (int j = i; j <= m; j++)
      range[i][j] = {-1, -1};
  for (int j = 1; j <= n; j++) {
    for (int i = 1; i <= m; i++) {
      lh[i] = i - 1;
      while (lh[i] > 0 && a[i][j] >= a[lh[i]][j])
        lh[i] = lh[lh[i]];
    }
    for (int i = m; i > 0; i--) {
      rh[i] = i + 1;
      while (rh[i] <= m && a[i][j] >= a[rh[i]][j])
        rh[i] = rh[rh[i]];
    }
    for (int i = 1; i <= m; i++) {
      int l = lh[i] + 1, r = rh[i] - 1;
      if (1 < l && l <= r && r < m && range[l][r].second != j) {
        if (range[l][r].second == j - 1)
          range[l][r].second++;
        else range[l][r] = {j, j};
        int len = range[l][r].second - range[l][r].first + 1;
        events[r][j].emplace_back(EventType::add, r - l + 1, len);
      }
    }
  }
  ll ans = 0;
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      auto &events = ::events[i][j];
      sort(events.begin(), events.end());
      for (const auto &event: events) {
        if (event.type == EventType::add) {
          cnt.update(event.c, +1);
        } else {
          ans += cnt.suff(event.c);
        }
      }
    	for (const auto &event: events) 
        if (event.type == EventType::add) 
          cnt.update(event.c, -1);
    }
  }
  return ans;
}
 
#ifdef LOCAL
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
 
	long long result = count_rectangles(a);
 
	cout << result;
	return 0;
}
#endif

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	150364 KB	Output is correct
2	Correct	32 ms	152268 KB	Output is correct
3	Correct	32 ms	152268 KB	Output is correct
4	Correct	32 ms	152420 KB	Output is correct
5	Correct	32 ms	152408 KB	Output is correct
6	Correct	32 ms	152284 KB	Output is correct
7	Correct	33 ms	152412 KB	Output is correct
8	Correct	33 ms	152396 KB	Output is correct
9	Correct	31 ms	152408 KB	Output is correct
10	Correct	33 ms	152400 KB	Output is correct
11	Correct	33 ms	152396 KB	Output is correct
12	Correct	33 ms	152412 KB	Output is correct
13	Correct	32 ms	150364 KB	Output is correct
14	Correct	32 ms	150612 KB	Output is correct
15	Correct	31 ms	150352 KB	Output is correct
16	Correct	32 ms	150356 KB	Output is correct
17	Correct	32 ms	150360 KB	Output is correct
18	Correct	31 ms	150392 KB	Output is correct
19	Correct	32 ms	152400 KB	Output is correct
20	Correct	32 ms	152412 KB	Output is correct
21	Correct	31 ms	150364 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	150364 KB	Output is correct
2	Correct	32 ms	152268 KB	Output is correct
3	Correct	32 ms	152268 KB	Output is correct
4	Correct	32 ms	152420 KB	Output is correct
5	Correct	32 ms	152408 KB	Output is correct
6	Correct	32 ms	152284 KB	Output is correct
7	Correct	33 ms	152412 KB	Output is correct
8	Correct	33 ms	152396 KB	Output is correct
9	Correct	31 ms	152408 KB	Output is correct
10	Correct	33 ms	152400 KB	Output is correct
11	Correct	33 ms	152396 KB	Output is correct
12	Correct	33 ms	152412 KB	Output is correct
13	Correct	32 ms	150364 KB	Output is correct
14	Correct	32 ms	150612 KB	Output is correct
15	Correct	31 ms	150352 KB	Output is correct
16	Correct	32 ms	150356 KB	Output is correct
17	Correct	32 ms	150360 KB	Output is correct
18	Correct	31 ms	150392 KB	Output is correct
19	Correct	32 ms	152400 KB	Output is correct
20	Correct	32 ms	152412 KB	Output is correct
21	Correct	31 ms	150364 KB	Output is correct
22	Correct	33 ms	154704 KB	Output is correct
23	Correct	33 ms	154708 KB	Output is correct
24	Correct	34 ms	154704 KB	Output is correct
25	Correct	33 ms	154460 KB	Output is correct
26	Correct	33 ms	154712 KB	Output is correct
27	Correct	34 ms	154716 KB	Output is correct
28	Correct	34 ms	154704 KB	Output is correct
29	Correct	33 ms	154628 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	150364 KB	Output is correct
2	Correct	32 ms	152268 KB	Output is correct
3	Correct	32 ms	152268 KB	Output is correct
4	Correct	32 ms	152420 KB	Output is correct
5	Correct	32 ms	152408 KB	Output is correct
6	Correct	32 ms	152284 KB	Output is correct
7	Correct	33 ms	152412 KB	Output is correct
8	Correct	33 ms	152396 KB	Output is correct
9	Correct	31 ms	152408 KB	Output is correct
10	Correct	33 ms	152400 KB	Output is correct
11	Correct	33 ms	152396 KB	Output is correct
12	Correct	33 ms	152412 KB	Output is correct
13	Correct	32 ms	150364 KB	Output is correct
14	Correct	32 ms	150612 KB	Output is correct
15	Correct	31 ms	150352 KB	Output is correct
16	Correct	32 ms	150356 KB	Output is correct
17	Correct	33 ms	154704 KB	Output is correct
18	Correct	33 ms	154708 KB	Output is correct
19	Correct	34 ms	154704 KB	Output is correct
20	Correct	33 ms	154460 KB	Output is correct
21	Correct	33 ms	154712 KB	Output is correct
22	Correct	34 ms	154716 KB	Output is correct
23	Correct	34 ms	154704 KB	Output is correct
24	Correct	33 ms	154628 KB	Output is correct
25	Correct	32 ms	150360 KB	Output is correct
26	Correct	31 ms	150392 KB	Output is correct
27	Correct	32 ms	152400 KB	Output is correct
28	Correct	32 ms	152412 KB	Output is correct
29	Correct	31 ms	150364 KB	Output is correct
30	Correct	36 ms	158292 KB	Output is correct
31	Correct	38 ms	158296 KB	Output is correct
32	Correct	37 ms	158292 KB	Output is correct
33	Correct	38 ms	157392 KB	Output is correct
34	Correct	41 ms	158300 KB	Output is correct
35	Correct	41 ms	158544 KB	Output is correct
36	Correct	41 ms	158544 KB	Output is correct
37	Correct	41 ms	158544 KB	Output is correct

Subtask #4
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	150364 KB	Output is correct
2	Correct	32 ms	152268 KB	Output is correct
3	Correct	32 ms	152268 KB	Output is correct
4	Correct	32 ms	152420 KB	Output is correct
5	Correct	32 ms	152408 KB	Output is correct
6	Correct	32 ms	152284 KB	Output is correct
7	Correct	33 ms	152412 KB	Output is correct
8	Correct	33 ms	152396 KB	Output is correct
9	Correct	31 ms	152408 KB	Output is correct
10	Correct	33 ms	152400 KB	Output is correct
11	Correct	33 ms	152396 KB	Output is correct
12	Correct	33 ms	152412 KB	Output is correct
13	Correct	32 ms	150364 KB	Output is correct
14	Correct	32 ms	150612 KB	Output is correct
15	Correct	31 ms	150352 KB	Output is correct
16	Correct	32 ms	150356 KB	Output is correct
17	Correct	33 ms	154704 KB	Output is correct
18	Correct	33 ms	154708 KB	Output is correct
19	Correct	34 ms	154704 KB	Output is correct
20	Correct	33 ms	154460 KB	Output is correct
21	Correct	33 ms	154712 KB	Output is correct
22	Correct	34 ms	154716 KB	Output is correct
23	Correct	34 ms	154704 KB	Output is correct
24	Correct	33 ms	154628 KB	Output is correct
25	Correct	36 ms	158292 KB	Output is correct
26	Correct	38 ms	158296 KB	Output is correct
27	Correct	37 ms	158292 KB	Output is correct
28	Correct	38 ms	157392 KB	Output is correct
29	Correct	41 ms	158300 KB	Output is correct
30	Correct	41 ms	158544 KB	Output is correct
31	Correct	41 ms	158544 KB	Output is correct
32	Correct	41 ms	158544 KB	Output is correct
33	Correct	32 ms	150360 KB	Output is correct
34	Correct	31 ms	150392 KB	Output is correct
35	Correct	32 ms	152400 KB	Output is correct
36	Correct	32 ms	152412 KB	Output is correct
37	Correct	31 ms	150364 KB	Output is correct
38	Correct	73 ms	187992 KB	Output is correct
39	Correct	80 ms	191824 KB	Output is correct
40	Correct	91 ms	191928 KB	Output is correct
41	Correct	89 ms	195152 KB	Output is correct
42	Correct	88 ms	196972 KB	Output is correct
43	Correct	87 ms	196944 KB	Output is correct
44	Correct	89 ms	197204 KB	Output is correct
45	Correct	98 ms	193900 KB	Output is correct
46	Correct	88 ms	183596 KB	Output is correct
47	Correct	102 ms	186120 KB	Output is correct
48	Correct	164 ms	197360 KB	Output is correct
49	Correct	167 ms	199480 KB	Output is correct
50	Correct	104 ms	186212 KB	Output is correct
51	Correct	97 ms	182124 KB	Output is correct
52	Correct	156 ms	197300 KB	Output is correct
53	Correct	171 ms	198048 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	197712 KB	Output is correct
2	Correct	38 ms	193484 KB	Output is correct
3	Correct	40 ms	197468 KB	Output is correct
4	Correct	32 ms	150360 KB	Output is correct
5	Correct	39 ms	197712 KB	Output is correct
6	Correct	40 ms	197724 KB	Output is correct
7	Correct	39 ms	197716 KB	Output is correct
8	Correct	39 ms	197828 KB	Output is correct
9	Correct	39 ms	197588 KB	Output is correct
10	Correct	39 ms	197476 KB	Output is correct
11	Correct	38 ms	197544 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	150360 KB	Output is correct
2	Correct	31 ms	150392 KB	Output is correct
3	Correct	32 ms	152400 KB	Output is correct
4	Correct	32 ms	152412 KB	Output is correct
5	Correct	31 ms	150364 KB	Output is correct
6	Correct	31 ms	150352 KB	Output is correct
7	Correct	378 ms	263776 KB	Output is correct
8	Correct	738 ms	355376 KB	Output is correct
9	Correct	732 ms	355924 KB	Output is correct
10	Correct	753 ms	356192 KB	Output is correct
11	Correct	122 ms	240212 KB	Output is correct
12	Correct	192 ms	278872 KB	Output is correct
13	Correct	211 ms	282760 KB	Output is correct

Subtask #7
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	150364 KB	Output is correct
2	Correct	32 ms	152268 KB	Output is correct
3	Correct	32 ms	152268 KB	Output is correct
4	Correct	32 ms	152420 KB	Output is correct
5	Correct	32 ms	152408 KB	Output is correct
6	Correct	32 ms	152284 KB	Output is correct
7	Correct	33 ms	152412 KB	Output is correct
8	Correct	33 ms	152396 KB	Output is correct
9	Correct	31 ms	152408 KB	Output is correct
10	Correct	33 ms	152400 KB	Output is correct
11	Correct	33 ms	152396 KB	Output is correct
12	Correct	33 ms	152412 KB	Output is correct
13	Correct	32 ms	150364 KB	Output is correct
14	Correct	32 ms	150612 KB	Output is correct
15	Correct	31 ms	150352 KB	Output is correct
16	Correct	32 ms	150356 KB	Output is correct
17	Correct	33 ms	154704 KB	Output is correct
18	Correct	33 ms	154708 KB	Output is correct
19	Correct	34 ms	154704 KB	Output is correct
20	Correct	33 ms	154460 KB	Output is correct
21	Correct	33 ms	154712 KB	Output is correct
22	Correct	34 ms	154716 KB	Output is correct
23	Correct	34 ms	154704 KB	Output is correct
24	Correct	33 ms	154628 KB	Output is correct
25	Correct	36 ms	158292 KB	Output is correct
26	Correct	38 ms	158296 KB	Output is correct
27	Correct	37 ms	158292 KB	Output is correct
28	Correct	38 ms	157392 KB	Output is correct
29	Correct	41 ms	158300 KB	Output is correct
30	Correct	41 ms	158544 KB	Output is correct
31	Correct	41 ms	158544 KB	Output is correct
32	Correct	41 ms	158544 KB	Output is correct
33	Correct	73 ms	187992 KB	Output is correct
34	Correct	80 ms	191824 KB	Output is correct
35	Correct	91 ms	191928 KB	Output is correct
36	Correct	89 ms	195152 KB	Output is correct
37	Correct	88 ms	196972 KB	Output is correct
38	Correct	87 ms	196944 KB	Output is correct
39	Correct	89 ms	197204 KB	Output is correct
40	Correct	98 ms	193900 KB	Output is correct
41	Correct	88 ms	183596 KB	Output is correct
42	Correct	102 ms	186120 KB	Output is correct
43	Correct	164 ms	197360 KB	Output is correct
44	Correct	167 ms	199480 KB	Output is correct
45	Correct	104 ms	186212 KB	Output is correct
46	Correct	97 ms	182124 KB	Output is correct
47	Correct	156 ms	197300 KB	Output is correct
48	Correct	171 ms	198048 KB	Output is correct
49	Correct	41 ms	197712 KB	Output is correct
50	Correct	38 ms	193484 KB	Output is correct
51	Correct	40 ms	197468 KB	Output is correct
52	Correct	32 ms	150360 KB	Output is correct
53	Correct	39 ms	197712 KB	Output is correct
54	Correct	40 ms	197724 KB	Output is correct
55	Correct	39 ms	197716 KB	Output is correct
56	Correct	39 ms	197828 KB	Output is correct
57	Correct	39 ms	197588 KB	Output is correct
58	Correct	39 ms	197476 KB	Output is correct
59	Correct	38 ms	197544 KB	Output is correct
60	Correct	31 ms	150352 KB	Output is correct
61	Correct	378 ms	263776 KB	Output is correct
62	Correct	738 ms	355376 KB	Output is correct
63	Correct	732 ms	355924 KB	Output is correct
64	Correct	753 ms	356192 KB	Output is correct
65	Correct	122 ms	240212 KB	Output is correct
66	Correct	192 ms	278872 KB	Output is correct
67	Correct	211 ms	282760 KB	Output is correct
68	Correct	32 ms	150360 KB	Output is correct
69	Correct	31 ms	150392 KB	Output is correct
70	Correct	32 ms	152400 KB	Output is correct
71	Correct	32 ms	152412 KB	Output is correct
72	Correct	31 ms	150364 KB	Output is correct
73	Correct	549 ms	413132 KB	Output is correct
74	Correct	667 ms	458292 KB	Output is correct
75	Correct	917 ms	458564 KB	Output is correct
76	Correct	926 ms	512696 KB	Output is correct
77	Correct	712 ms	485708 KB	Output is correct
78	Correct	1060 ms	400400 KB	Output is correct
79	Correct	1131 ms	429076 KB	Output is correct
80	Correct	1783 ms	535520 KB	Output is correct
81	Correct	1118 ms	417284 KB	Output is correct
82	Correct	1485 ms	495412 KB	Output is correct
83	Correct	1878 ms	564236 KB	Output is correct
84	Correct	1046 ms	398492 KB	Output is correct
85	Correct	1990 ms	546412 KB	Output is correct
86	Correct	1725 ms	535756 KB	Output is correct
87	Correct	438 ms	384016 KB	Output is correct
88	Correct	696 ms	485440 KB	Output is correct
89	Correct	689 ms	485584 KB	Output is correct
90	Correct	689 ms	485700 KB	Output is correct

답안 #844763

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 7.0 / 7.0

Subtask #3 12.0 / 12.0

Subtask #4 22.0 / 22.0

Subtask #5 10.0 / 10.0

Subtask #6 13.0 / 13.0

Subtask #7 28.0 / 28.0

Subtask #1
8.0 / 8.0

Subtask #2
7.0 / 7.0

Subtask #3
12.0 / 12.0

Subtask #4
22.0 / 22.0

Subtask #5
10.0 / 10.0

Subtask #6
13.0 / 13.0

Subtask #7
28.0 / 28.0