oj.uz

Submission #817658

# Submission time Handle Problem Language Result Execution time Memory
817658 2023-08-09T14:42:00 Z prvocislo Rectangles (IOI19_rect) C++17
100 / 100
 4030 ms 607904 KB 
#include "rect.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 2505;
vector<int> e[maxn][maxn];
int ri[maxn], li[maxn];
ll ans = 0;
struct obdl
{
	int x1, y1, x2, y2, t;
};
void make(const vector<vector<int> > &a, vector<obdl> &o, int t)
{
	int n = a.size(), m = a[0].size();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++) ri[j] = m, li[j] = -1;
		vector<int> st;
		for (int j = 0; j < m; j++) // najdeme najblizsi vacsi
		{
			while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
			if (!st.empty() && st.back() + 1 < j) li[j] = st.back();
			st.push_back(j);
		}
		st.clear();
		for (int j = m - 1; j >= 0; j--) // najdeme najblizsi vacsi
		{
			while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
			if (!st.empty() && st.back() - 1 > j) ri[j] = st.back();
			st.push_back(j);
		}
		for (int j = 0; j < m; j++)
		{
			if (ri[j] != m && li[ri[j]] <= j) e[j + 1][ri[j] - 1].push_back(i);
			if (li[j] != -1 && ri[li[j]] >= j) e[li[j] + 1][j - 1].push_back(i);
		}
	}
	for (int y1 = 0; y1 < m; y1++) for (int y2 = y1; y2 < m; y2++)
	{
		for (int i = 0; i < e[y1][y2].size(); i++) if (!i || e[y1][y2][i - 1] + 1 < e[y1][y2][i])
		{
			int j = i;
			while (j + 1 < e[y1][y2].size() && e[y1][y2][j] >= e[y1][y2][j + 1] - 1) j++;
			o.push_back({ e[y1][y2][i], y1, e[y1][y2][j], y2, t });
		}
		e[y1][y2].clear();
	}
}
int st[maxn];
void upd(int i, int x)
{
	for (; i < maxn; i = (i | (i + 1))) st[i] += x;
}
int query(int r)
{
	int ans = 0;
	for (; r >= 0; r = (r & (r + 1)) - 1) ans += st[r];
	return ans;
}
bool cmp(obdl a, obdl b)
{
	if (a.x2 == b.x2) return a.t > b.t;
	return a.x2 < b.x2;
}
ll count_rectangles(vector<vector<int> > a)
{
	int n = a.size(), m = a[0].size();
	vector<obdl> ob;
	vector<vector<int> > b(m, vector<int>(n));
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[j][i] = a[i][j];
	make(b, ob, 2);
	for (obdl& i : ob) swap(i.x1, i.y1), swap(i.x2, i.y2);
	make(a, ob, 1);
	sort(ob.begin(), ob.end(), cmp);
	for (int i = 0; i < ob.size(); i++)
	{
		if (ob[i].t == 1) for (int x1 = ob[i].x1; x1 <= ob[i].x2; x1++) e[x1][ob[i].y1].push_back(i);
		if (ob[i].t == 2) for (int y1 = ob[i].y1; y1 <= ob[i].y2; y1++) e[ob[i].x1][y1].push_back(i);
	}
	ll ans = 0;
	for (int x = 1; x + 1 < n; x++) for (int y = 1; y + 1 < m; y++)
	{
		ll sum = 0, all = 0;
		for (int u : e[x][y])
		{
			if (ob[u].t == 2) upd(ob[u].y2, 1), all++;
			else sum += all - query(ob[u].y2 - 1);
		}
		for (int u : e[x][y]) if (ob[u].t == 2) upd(ob[u].y2, -1);
		ans += sum;
		//cout << sum << " \n"[y == m - 2];
	}
	return ans;
}

Compilation message

rect.cpp: In function 'void make(const std::vector<std::vector<int> >&, std::vector<obdl>&, int)':
rect.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 0; i < e[y1][y2].size(); i++) if (!i || e[y1][y2][i - 1] + 1 < e[y1][y2][i])
      |                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    while (j + 1 < e[y1][y2].size() && e[y1][y2][j] >= e[y1][y2][j + 1] - 1) j++;
      |           ~~~~~~^~~~~~~~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<obdl>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 0; i < ob.size(); i++)
      |                  ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 147648 KB Output is correct
2 Correct 64 ms 147616 KB Output is correct
3 Correct 65 ms 147616 KB Output is correct
4 Correct 67 ms 147612 KB Output is correct
5 Correct 67 ms 147628 KB Output is correct
6 Correct 73 ms 147772 KB Output is correct
7 Correct 74 ms 147572 KB Output is correct
8 Correct 66 ms 147660 KB Output is correct
9 Correct 66 ms 147680 KB Output is correct
10 Correct 66 ms 147644 KB Output is correct
11 Correct 65 ms 147648 KB Output is correct
12 Correct 66 ms 147640 KB Output is correct
13 Correct 65 ms 147572 KB Output is correct
14 Correct 66 ms 147580 KB Output is correct
15 Correct 66 ms 147660 KB Output is correct
16 Correct 65 ms 147572 KB Output is correct
17 Correct 65 ms 147608 KB Output is correct
18 Correct 66 ms 147540 KB Output is correct
19 Correct 66 ms 147656 KB Output is correct
20 Correct 67 ms 147544 KB Output is correct
21 Correct 66 ms 147600 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 147648 KB Output is correct
2 Correct 64 ms 147616 KB Output is correct
3 Correct 65 ms 147616 KB Output is correct
4 Correct 67 ms 147612 KB Output is correct
5 Correct 67 ms 147628 KB Output is correct
6 Correct 73 ms 147772 KB Output is correct
7 Correct 74 ms 147572 KB Output is correct
8 Correct 66 ms 147660 KB Output is correct
9 Correct 66 ms 147680 KB Output is correct
10 Correct 66 ms 147644 KB Output is correct
11 Correct 65 ms 147648 KB Output is correct
12 Correct 66 ms 147640 KB Output is correct
13 Correct 65 ms 147572 KB Output is correct
14 Correct 66 ms 147580 KB Output is correct
15 Correct 66 ms 147660 KB Output is correct
16 Correct 65 ms 147572 KB Output is correct
17 Correct 65 ms 147608 KB Output is correct
18 Correct 66 ms 147540 KB Output is correct
19 Correct 66 ms 147656 KB Output is correct
20 Correct 67 ms 147544 KB Output is correct
21 Correct 66 ms 147600 KB Output is correct
22 Correct 67 ms 147960 KB Output is correct
23 Correct 71 ms 148036 KB Output is correct
24 Correct 72 ms 148140 KB Output is correct
25 Correct 68 ms 147948 KB Output is correct
26 Correct 68 ms 148264 KB Output is correct
27 Correct 69 ms 148292 KB Output is correct
28 Correct 71 ms 148172 KB Output is correct
29 Correct 68 ms 147844 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 147648 KB Output is correct
2 Correct 64 ms 147616 KB Output is correct
3 Correct 65 ms 147616 KB Output is correct
4 Correct 67 ms 147612 KB Output is correct
5 Correct 67 ms 147628 KB Output is correct
6 Correct 73 ms 147772 KB Output is correct
7 Correct 74 ms 147572 KB Output is correct
8 Correct 66 ms 147660 KB Output is correct
9 Correct 66 ms 147680 KB Output is correct
10 Correct 66 ms 147644 KB Output is correct
11 Correct 65 ms 147648 KB Output is correct
12 Correct 66 ms 147640 KB Output is correct
13 Correct 65 ms 147572 KB Output is correct
14 Correct 66 ms 147580 KB Output is correct
15 Correct 66 ms 147660 KB Output is correct
16 Correct 65 ms 147572 KB Output is correct
17 Correct 67 ms 147960 KB Output is correct
18 Correct 71 ms 148036 KB Output is correct
19 Correct 72 ms 148140 KB Output is correct
20 Correct 68 ms 147948 KB Output is correct
21 Correct 68 ms 148264 KB Output is correct
22 Correct 69 ms 148292 KB Output is correct
23 Correct 71 ms 148172 KB Output is correct
24 Correct 68 ms 147844 KB Output is correct
25 Correct 65 ms 147608 KB Output is correct
26 Correct 66 ms 147540 KB Output is correct
27 Correct 66 ms 147656 KB Output is correct
28 Correct 67 ms 147544 KB Output is correct
29 Correct 66 ms 147600 KB Output is correct
30 Correct 72 ms 149828 KB Output is correct
31 Correct 74 ms 149708 KB Output is correct
32 Correct 73 ms 149920 KB Output is correct
33 Correct 76 ms 149504 KB Output is correct
34 Correct 88 ms 150684 KB Output is correct
35 Correct 87 ms 150856 KB Output is correct
36 Correct 82 ms 150408 KB Output is correct
37 Correct 85 ms 150448 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 147648 KB Output is correct
2 Correct 64 ms 147616 KB Output is correct
3 Correct 65 ms 147616 KB Output is correct
4 Correct 67 ms 147612 KB Output is correct
5 Correct 67 ms 147628 KB Output is correct
6 Correct 73 ms 147772 KB Output is correct
7 Correct 74 ms 147572 KB Output is correct
8 Correct 66 ms 147660 KB Output is correct
9 Correct 66 ms 147680 KB Output is correct
10 Correct 66 ms 147644 KB Output is correct
11 Correct 65 ms 147648 KB Output is correct
12 Correct 66 ms 147640 KB Output is correct
13 Correct 65 ms 147572 KB Output is correct
14 Correct 66 ms 147580 KB Output is correct
15 Correct 66 ms 147660 KB Output is correct
16 Correct 65 ms 147572 KB Output is correct
17 Correct 67 ms 147960 KB Output is correct
18 Correct 71 ms 148036 KB Output is correct
19 Correct 72 ms 148140 KB Output is correct
20 Correct 68 ms 147948 KB Output is correct
21 Correct 68 ms 148264 KB Output is correct
22 Correct 69 ms 148292 KB Output is correct
23 Correct 71 ms 148172 KB Output is correct
24 Correct 68 ms 147844 KB Output is correct
25 Correct 72 ms 149828 KB Output is correct
26 Correct 74 ms 149708 KB Output is correct
27 Correct 73 ms 149920 KB Output is correct
28 Correct 76 ms 149504 KB Output is correct
29 Correct 88 ms 150684 KB Output is correct
30 Correct 87 ms 150856 KB Output is correct
31 Correct 82 ms 150408 KB Output is correct
32 Correct 85 ms 150448 KB Output is correct
33 Correct 65 ms 147608 KB Output is correct
34 Correct 66 ms 147540 KB Output is correct
35 Correct 66 ms 147656 KB Output is correct
36 Correct 67 ms 147544 KB Output is correct
37 Correct 66 ms 147600 KB Output is correct
38 Correct 217 ms 181336 KB Output is correct
39 Correct 202 ms 179028 KB Output is correct
40 Correct 188 ms 178968 KB Output is correct
41 Correct 167 ms 176676 KB Output is correct
42 Correct 171 ms 174828 KB Output is correct
43 Correct 164 ms 177680 KB Output is correct
44 Correct 181 ms 175268 KB Output is correct
45 Correct 170 ms 176308 KB Output is correct
46 Correct 153 ms 165956 KB Output is correct
47 Correct 201 ms 170140 KB Output is correct
48 Correct 319 ms 184768 KB Output is correct
49 Correct 346 ms 186904 KB Output is correct
50 Correct 202 ms 168000 KB Output is correct
51 Correct 207 ms 167932 KB Output is correct
52 Correct 322 ms 181220 KB Output is correct
53 Correct 303 ms 182300 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 148412 KB Output is correct
2 Correct 80 ms 148184 KB Output is correct
3 Correct 82 ms 147872 KB Output is correct
4 Correct 69 ms 147556 KB Output is correct
5 Correct 93 ms 148300 KB Output is correct
6 Correct 93 ms 148376 KB Output is correct
7 Correct 84 ms 148416 KB Output is correct
8 Correct 81 ms 148248 KB Output is correct
9 Correct 83 ms 148424 KB Output is correct
10 Correct 79 ms 147940 KB Output is correct
11 Correct 81 ms 148276 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 147608 KB Output is correct
2 Correct 66 ms 147540 KB Output is correct
3 Correct 66 ms 147656 KB Output is correct
4 Correct 67 ms 147544 KB Output is correct
5 Correct 66 ms 147600 KB Output is correct
6 Correct 75 ms 147596 KB Output is correct
7 Correct 712 ms 260180 KB Output is correct
8 Correct 1412 ms 381760 KB Output is correct
9 Correct 1338 ms 382876 KB Output is correct
10 Correct 1336 ms 382936 KB Output is correct
11 Correct 183 ms 190128 KB Output is correct
12 Correct 290 ms 228236 KB Output is correct
13 Correct 303 ms 233564 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 147648 KB Output is correct
2 Correct 64 ms 147616 KB Output is correct
3 Correct 65 ms 147616 KB Output is correct
4 Correct 67 ms 147612 KB Output is correct
5 Correct 67 ms 147628 KB Output is correct
6 Correct 73 ms 147772 KB Output is correct
7 Correct 74 ms 147572 KB Output is correct
8 Correct 66 ms 147660 KB Output is correct
9 Correct 66 ms 147680 KB Output is correct
10 Correct 66 ms 147644 KB Output is correct
11 Correct 65 ms 147648 KB Output is correct
12 Correct 66 ms 147640 KB Output is correct
13 Correct 65 ms 147572 KB Output is correct
14 Correct 66 ms 147580 KB Output is correct
15 Correct 66 ms 147660 KB Output is correct
16 Correct 65 ms 147572 KB Output is correct
17 Correct 67 ms 147960 KB Output is correct
18 Correct 71 ms 148036 KB Output is correct
19 Correct 72 ms 148140 KB Output is correct
20 Correct 68 ms 147948 KB Output is correct
21 Correct 68 ms 148264 KB Output is correct
22 Correct 69 ms 148292 KB Output is correct
23 Correct 71 ms 148172 KB Output is correct
24 Correct 68 ms 147844 KB Output is correct
25 Correct 72 ms 149828 KB Output is correct
26 Correct 74 ms 149708 KB Output is correct
27 Correct 73 ms 149920 KB Output is correct
28 Correct 76 ms 149504 KB Output is correct
29 Correct 88 ms 150684 KB Output is correct
30 Correct 87 ms 150856 KB Output is correct
31 Correct 82 ms 150408 KB Output is correct
32 Correct 85 ms 150448 KB Output is correct
33 Correct 217 ms 181336 KB Output is correct
34 Correct 202 ms 179028 KB Output is correct
35 Correct 188 ms 178968 KB Output is correct
36 Correct 167 ms 176676 KB Output is correct
37 Correct 171 ms 174828 KB Output is correct
38 Correct 164 ms 177680 KB Output is correct
39 Correct 181 ms 175268 KB Output is correct
40 Correct 170 ms 176308 KB Output is correct
41 Correct 153 ms 165956 KB Output is correct
42 Correct 201 ms 170140 KB Output is correct
43 Correct 319 ms 184768 KB Output is correct
44 Correct 346 ms 186904 KB Output is correct
45 Correct 202 ms 168000 KB Output is correct
46 Correct 207 ms 167932 KB Output is correct
47 Correct 322 ms 181220 KB Output is correct
48 Correct 303 ms 182300 KB Output is correct
49 Correct 95 ms 148412 KB Output is correct
50 Correct 80 ms 148184 KB Output is correct
51 Correct 82 ms 147872 KB Output is correct
52 Correct 69 ms 147556 KB Output is correct
53 Correct 93 ms 148300 KB Output is correct
54 Correct 93 ms 148376 KB Output is correct
55 Correct 84 ms 148416 KB Output is correct
56 Correct 81 ms 148248 KB Output is correct
57 Correct 83 ms 148424 KB Output is correct
58 Correct 79 ms 147940 KB Output is correct
59 Correct 81 ms 148276 KB Output is correct
60 Correct 75 ms 147596 KB Output is correct
61 Correct 712 ms 260180 KB Output is correct
62 Correct 1412 ms 381760 KB Output is correct
63 Correct 1338 ms 382876 KB Output is correct
64 Correct 1336 ms 382936 KB Output is correct
65 Correct 183 ms 190128 KB Output is correct
66 Correct 290 ms 228236 KB Output is correct
67 Correct 303 ms 233564 KB Output is correct
68 Correct 65 ms 147608 KB Output is correct
69 Correct 66 ms 147540 KB Output is correct
70 Correct 66 ms 147656 KB Output is correct
71 Correct 67 ms 147544 KB Output is correct
72 Correct 66 ms 147600 KB Output is correct
73 Correct 2617 ms 544068 KB Output is correct
74 Correct 2858 ms 512956 KB Output is correct
75 Correct 2016 ms 513196 KB Output is correct
76 Correct 1688 ms 489772 KB Output is correct
77 Correct 1631 ms 460552 KB Output is correct
78 Correct 2373 ms 440296 KB Output is correct
79 Correct 2545 ms 448316 KB Output is correct
80 Correct 3955 ms 601064 KB Output is correct
81 Correct 2468 ms 431048 KB Output is correct
82 Correct 3243 ms 530832 KB Output is correct
83 Correct 4030 ms 607904 KB Output is correct
84 Correct 1976 ms 392712 KB Output is correct
85 Correct 3362 ms 554028 KB Output is correct
86 Correct 3153 ms 540720 KB Output is correct
87 Correct 1119 ms 352436 KB Output is correct
88 Correct 1561 ms 457028 KB Output is correct
89 Correct 1553 ms 457312 KB Output is correct
90 Correct 1562 ms 457196 KB Output is correct